Why RE?
查看原帖
Why RE?
763878
Jerry_heng楼主2024/7/6 17:59
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
const int bas=13,md=1e9+7,mxn=2e5+10;;
string st[3];
int a[10],n,q,pw[mxn],pws[mxn],tag[mxn<<2],val[mxn<<2];
int change(char ch){
	if(ch=='J')return 0;
	else if(ch=='O')return 1;
	else return 2;
}
int solve(string s){
	int res=0;
	for(int i=1;i<=n;i++)
		res=(res*bas%md+change(s[i-1]))%md;
	return res;
}
bool pd(int x){
	for(int i=1;i<=9;i++)
		if(a[i]==x)return 1;
	return 0;
}
string cross(string x,string y){
	string z="";
	for(int i=0;i<n;i++)
		if(x[i]==y[i])z[i]=x[i];
		else{
			int s=3-change(x[i])-change(y[i]);
			if(s==0)z[i]='J';
			else if(s==1)z[i]='O';
			else z[i]='I';
		}
	return z;
}
void build(int o,int l,int r){
	tag[o]=-1;
	if(l==r){
		val[o]=change(st[0][l-1]);
		return;
	}
	int mid=(l+r)>>1;
	build(o*2,l,mid);
	build(o*2+1,mid+1,r);
	val[o]=(val[o*2]*pw[r-mid]%md+val[o*2+1])%md;
}
void pushdown(int o,int l,int r){
	if(tag[o]==-1)return;
	tag[o*2]=tag[o*2+1]=tag[o];
	tag[o]=-1;
	int mid=(l+r)>>1;
	val[o*2]=tag[o*2]*pws[mid-l]%md;
	val[o*2+1]=tag[o*2+1]*pws[r-mid-1]%md;
}
void update(int o,int l,int r,int L,int R,int num){
	if(L<=l&&r<=R){
		tag[o]=num;
		val[o]=num*pws[r-l]%md;
		return;
	}
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if(L<=mid)update(o*2,l,mid,L,R,num);
	if(R>mid)update(o*2+1,mid+1,r,L,R,num);
	val[o]=(val[o*2]*pw[r-mid]%md+val[o*2+1])%md;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	pw[0]=pws[0]=1;
	for(int i=1;i<=n;i++){
		pw[i]=pw[i-1]*bas%md;
		pws[i]=(pws[i-1]+pw[i])%md;
	}
	cin>>st[0]>>st[1]>>st[2];
	a[1]=solve(st[0]),a[2]=solve(st[1]),a[3]=solve(st[2]);
	a[4]=solve(cross(st[0],st[1])),
	a[5]=solve(cross(st[0],st[2])),
	a[6]=solve(cross(st[2],st[1])),
	a[7]=solve(cross(st[0],cross(st[1],st[2]))),
	a[8]=solve(cross(st[1],cross(st[2],st[0]))),
	a[9]=solve(cross(st[2],cross(st[1],st[0])));
	cin>>q;
	cin>>st[0];
	build(1,1,n);
	puts(pd(val[1])?"Yes":"No");
	while(q--){
		char ch;
		int l,r;
		cin>>l>>r>>ch;
		update(1,1,n,l,r,change(ch));
		puts(pd(val[1])?"Yes":"No");
	}
    return 0;
}
2024/7/6 17:59
加载中...