珂树玄关求条
查看原帖
珂树玄关求条
663199
Tachibana27楼主2024/10/8 16:53
#include<bits/stdc++.h>
#define DEBUG false
#define XLTX true
#define FILE_ false
#define int long long
#define iit std::set<node>::iterator
#if DEBUG
	bool Memory_Start;
    void Deb();

#endif

#if XLTX
	inline int read(){
		int s=0;
		int w=1;
		char ch=getchar();
		for(;ch<'0'||ch>'9';ch=getchar())
	    	if(ch=='-')
				w=-1;
		for(;ch>='0' and ch<='9';ch=getchar())
			s=s*10+ch-'0';
		return s*w;
	}
	void write(int x){
		if(x<0){
			putchar('-');
			x=-x;
		}
		if(x>9)
	    	write(x/10);
		putchar(x%10+'0');
		return;
	}
#else
	inline int read(){
		int reader;
		std::cin>>reader;
		return reader;
	}
	void write(int x){
		std::cout<<x;
		return;
	}
#endif

void file_(std::string s,bool flag){
	if(not flag)
		return;
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
	return;
}
class node{
	public:
		int l,r;
		mutable int v;
		node(int L=0,int R=-1,int V=0):l(L),r(R),v(V){}
		friend bool operator<(node a,node b){
			return a.l<b.l;
		}
};
std::set<node>s;
iit split(int pos){
	iit qwq=s.lower_bound(pos);
	if(qwq!=s.end() and (qwq->l)==pos)
		return qwq;
	qwq--;
	if(pos>(qwq->r))
		return s.end();
	int ll=(qwq->l);
	int rr=(qwq->r);
	int vv=(qwq->v);
	s.erase(qwq);
	s.insert(node(ll,pos-1,vv));
	return s.insert(node(pos,rr,vv)).first;
}
int t;

int n;
int q;
int a[1000086];
void assign(int l,int r,int v){
	iit rr=split(r+1);
	iit ll=split(l);
	s.erase(ll,rr);
	s.insert(node(l,r,v));
	return;
}
inline iit pre(iit pos){
	return --pos;
}
inline iit nxt(iit pos){
	return ++pos;
}
bool ask(int l,int r){
	iit rr=split(r+1);
	iit ll=split(l);
	if(ll!=rr)
		return false;
//	puts("ll==rr"); 
	if(l==1 or r==n)
		return true;
	
//	std::cout<<(ll->l)<<" "<<(rr->l)<<"\n";
//	iit l_=--ll;
//	ll++;
//	iit r_=++rr;
//	rr--;
	if(l>(ll->l) and r<(rr->r))
		return false;
	if(l==(ll->l) and r!=(rr->r))
		return (pre(ll)->v)!=(rr->v);
	if(l!=(ll->l) and r==(rr->r))
		return (nxt(ll)->v)!=(rr->v);
	return (pre(ll)->v)!=(nxt(rr)->v);
	
}
signed main(){
	file_("",FILE_);
//	t=read();
	t=1;
	while(t--){
		//code here
		n=read();
		for(int i=1;i<=n;i++){
			char c;
			std::cin>>c;
			a[i]=c-'A'+1;
		}
		int ll=1;
//		int rr=1;
		int v=a[1];
		for(int i=2;i<=n+1;i++)
			if(a[i]!=v){
//				std::cout<<"insert: "<<ll<<" "<<i-1<<" "<<v<<"\n";
				s.insert(node(ll,i-1,v));
				ll=i;
				v=a[i];
			}
		q=read();
		while(q--){
			char cz;
			std::cin>>cz;
			if(cz=='A'){
				int x,y;
				char op;
				x=read();
				y=read();
				std::cin>>op;
				assign(x,y,op-'A'+1);
			}
			else{
				int x,y;
				x=read();
				y=read();
				if(ask(x,y))
					puts("Yes");
				else
					puts("No");
			}
		}
	}

#if DEBUG
    Deb();
#endif
    return 0;
}
#if DEBUG
bool Memory_End;
void Deb(){
	std::cout<<"Time: "<<clock()<<" ms\nMemory: "<<abs(&Memory_End-&Memory_Start)/1024.0/1024.0<<" Mb";
	return;
}
#endif

//Tachibana27 done it ...

rt,好像全部输出 no,玄 3 关

2024/10/8 16:53
加载中...