线段树样例过了全re求助
查看原帖
线段树样例过了全re求助
1268678
thrniseven楼主2024/9/6 00:40
#include<bits/stdc++.h>
#include<unordered_map>
#define Mid l+((r-l)>>1)
#define lf i<<1
#define rf i<<1|1
using namespace std;
const int N = 500001;
char arr[4 * N];

char c[N];
bool update[4 * N];
int n,m;
void up(int l, int r, int i) {
	arr[i] = arr[lf] & arr[rf];
	arr[i] = arr[i] == arr[lf] ? arr[lf] : 0;
}
void lazy(int i,char v) {
	arr[i] = v;
	
	update[i] = 1;
}
void down(int l, int r, int i) {
	if (update[i]) {
		lazy(lf, arr[i]);
		lazy(rf, arr[i]);
		update[i] = 0;
	}
}
void cg(int l, int r,  int v,int i,int jl, int jr ) {
	if (jl <= l && jr >= r) {
		lazy(i, v);
	}
	else {
		down(l, r, i);
		cg(l, Mid, v, lf, jl, jr);
		cg(Mid + 1, r, v, rf, jl, jr);
		up(l, r, i);
	}
}
char query(int l,int r,int i,int jl,int jr) {
	if (jl <= l && jr >= r) {
		return arr[i];
	}
	else {
		char p1=-1, p2=-1;
		down(l, r, i);
		if (jl <= Mid)
		 p1=query(l, Mid, lf, jl, jr);
		if(jr>Mid)
		 p2 = query(Mid+1, r, rf, jl, jr);
		if (p1 != -1 && p2 != -1) {
			return (p1 == p2 && p1 != 0)?p1:0;
		}
		else {
			if (p1 == p2)return 0;
			else {
				return p1 == -1 ? p2 : p1;
			}
		}
	}
}
void built(int l, int r, int i) {
	if (l == r) {
		arr[i] = c[l];
	}
	else {
		built(l, Mid, lf);
		built(Mid + 1, r, rf);
		up(l,r,i);
	}
}
int main() {
	/*15
		AACBBABBBCCCBBB
		3
		B 4 5
		B 5 5
		B 10 12*/
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	built(1, n,1);
	cin >> m;
	
	for (int k = 0; k < m; k++) {
		char op;
		int l, r;
		cin >> op >> l >> r;
		if (op == 'B') {
			if (l!=1&&r!=n&&c[l - 1] == c[r + 1]) {
				cout << "No"<<"\n";
			}
			else
			{
				int ans = query(1, n, 1, l, r);
				cout << (ans > 0 ? "Yes" : "No") << "\n";
			}
		}
		else {
			char v;
			cin >> v;
			cg(1, n,v, 1, l, r);
		}

	}
}
2024/9/6 00:40
加载中...