终极珂学福利!
查看原帖
终极珂学福利!
28910
览遍千秋七海楼主2019/11/3 20:21

珂朵莉树全RE了。。。

求助

#include<bits/stdc++.h>
using namespace std;

#define IT set<node>::iterator

template <typename Tp>
void read(Tp &x){
	x=0;char ch=1;int fh;
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-'){fh=-1;ch=getchar();	}
	else fh=1;
	while(ch>='0'&&ch<='9')	x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	x*=fh;
}

const int maxn=500007;

struct node{
	int l,r;
	mutable int v;
	node(int L,int R=-1,int V=0):l(L),r(L),v(V){}
	bool operator <(node a)const{
		return l<a.l;
	}
};

char a[maxn];
set<node>s;

IT split(int pos){
	IT it=s.lower_bound(node(pos));
	if(it!=s.end()&&it->l==pos) return it;
	--it;
	int L=it->l,R=it->r,V=it->v;
	s.erase(it);s.insert(node(L,pos-1,V));
	return s.insert(node(pos,R,V)).first;
}

void assign(int l,int r,int val){
	IT rr=split(r+1),ll=split(l);
	s.erase(ll,rr);s.insert(node(l,r,val));
}

int gec(int pos){
	IT it=split(pos);
	return it->v;
}

bool check(int l,int r){
	IT rr=split(r+1),ll=split(l);
	int k=ll->v;
	for(;ll!=rr;++ll) if(ll->v!=k) return false;
	return true;
}

int T,x,y,z,n;
char c;
int main(){
	cin>>n>>(a+1)>>T;
	int cnt=1;char las=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]==las) ++cnt;
		else{
			s.insert(node(i-cnt,i-1,las));las=a[i],cnt=1;
		}
	}
	s.insert(node(n+1-cnt,n,las));
	while(T--){
		cin>>c;int op=c-'A'+1;
		if(op==1){
			read(x);read(y);read(z);
			assign(x,y,z);
		}
		else{
			read(x);read(y);
			if(x==1||x==n||y==1||y==n){
				if(check(x,y)) puts("Yes");
				else puts("No");
			}
			else{
				int aa=gec(x-1),bb=gec(y+1);
				if(aa==bb||!check(x,y)) puts("No");
				else puts("Yes");
			}
		}
	}
	return 0;
}
2019/11/3 20:21
加载中...