线段树 全T
查看原帖
线段树 全T
554584
thlm楼主2023/8/23 17:11
#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define mn 5000100

using namespace std;

inline int read(){

	int x=0;

	char ch=getchar();

	while('0'>ch || ch>'9') ch=getchar();

	while('0'<=ch && ch<='9')

		x=x*10+(ch-'0'),ch=getchar();

	return x;

};

int n,k,f[mn];

struct name{

	int l,r;

	int zl;

}a[mn*4];

void build(int x,int y,int b){

	a[b].l=x;a[b].r=y;

	if(x==y) {a[b].zl=f[x];return;}

	int mid=(x+y)>>1;

	build(x,mid,b<<1);build(mid+1,y,b<<1|1);

	a[b].zl=a[b<<1].zl&a[b<<1|1].zl;

};

void spread(int b){

	if(a[b].zl){

		a[b<<1].zl=a[b].zl;a[b<<1|1].zl=a[b].zl;

		a[b].zl=0;

	}

};

void change(int x,int y,int b,int op){

	if(a[b].l>=x && a[b].r<=y){

		a[b].zl=op;return;

	}

	spread(b);

	int mid=(a[b].l+a[b].r)>>1;

	if(x<=mid) change(x,y,b<<1,op);

	if(mid+1<=y) change(x,y,b<<1|1,op);

	a[b].zl=a[b<<1].zl&a[b<<1|1].zl;

};

int find(int x,int y,int b){

	if(a[b].zl) return a[b].zl;

	if(a[b].l>=x && a[b].r<=y) return a[b].zl;

	spread(b);

	int mid=(a[b].l+a[b].r)>>1;

	int le=-1,ri=-1;

	if(x<=mid) le=find(x,y,b<<1);

	if(mid+1<=y) ri=find(x,y,b<<1|1);

	a[b].zl=a[b<<1].zl&a[b<<1|1].zl;

	if(le!=-1 && ri!=-1){

		return le&ri;

	}else{

		return max(le,ri);

	}

};

int main(){

//	freopen("1.in","r",stdin);

//	freopen("1.out","w",stdout);

	n=read();

	for(int i=1;i<=n;i++){

		char ch;

		cin>>ch;

		f[i]=(1<<(ch-'0'));

	}

	build(1,n,1);k=read();

	for(int i=1;i<=k;i++){

		char opt;

		cin>>opt;

		if(opt=='A'){

			int x=read(),y=read(),op=read();

			change(x,y,1,op);

		}else{

			int x=read(),y=read();

			int ans=find(x,y,1);

			int la,ne;

			if(ans){

				if(x>1 && y<n){

					la=find(x-1,x-1,1);ne=find(y+1,y+1,1);

					if(la!=ne) puts("Yes");

					else puts("No");

				}else puts("Yes");

			}else{

				puts("No");

			}

		}

	}

	return 0;

}
2023/8/23 17:11
加载中...