2023.11.10联赛 T4题解
题目大意
题目思路
我们考虑分块处理。
我们可以维护一个状态，表示块内每个字母对应的真实字母，因为只有 3 3 3个字母，所以只有 6 6 6种情况。
对于每一个块，我们可以对于每种状态、每种块，预处理出以 A A A或 B B B或 C C C进入出来时是什么字母。
至此，思路就很明了。
修改操作对于散块直接修改，对于整块修改他们的状态。
查询操作对于散块直接跳，对于整块直接用预处理的信息跳即可。
具体实现参考代码。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,q,a[N],b[N],pos[N],posl[N],posr[N],g[N],sum[N][10][5],p[10][5],vis[5][5][5],block=0,tot=0;
char s[N],s1[200+10],s2[200+10];
int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();return s*w;
}
int work(int l,int r,int state,int x)
{for(int i=l;i<=r;++i){int val=p[state][a[i]];if(x%3+1!=val)x=val;}return x;
}
void change(int l,int r,int val1,int val2)
{int x=0,y=0;for(int i=1;i<=3;++i)if(p[g[pos[l]]][i]==val1)x=i; for(int i=1;i<=3;++i)if(p[g[pos[l]]][i]==val2)y=i; for(int i=l;i<=r;++i){if(p[g[pos[l]]][a[i]]==val1)a[i]=y;else if(p[g[pos[l]]][a[i]]==val2)a[i]=x;}for(int i=1;i<=6;++i) for(int j=1;j<=3;++j)sum[pos[l]][i][j]=work(posl[pos[l]],posr[pos[r]],i,j);
}
void update(int l,int r,int val1,int val2)
{if(pos[l]==pos[r]){change(l,r,val1,val2);return ;}change(l,posr[pos[l]],val1,val2);for(int i=pos[l]+1;i<=pos[r]-1;++i){int c[5];for(int j=1;j<=3;++j){if(p[g[i]][j]==val1)c[j]=val2;else if(p[g[i]][j]==val2)c[j]=val1;elsec[j]=p[g[i]][j];}g[i]=vis[c[1]][c[2]][c[3]];}change(posl[pos[r]],r,val1,val2);
}
int ask(int l,int r,int x)
{if(pos[l]==pos[r])return work(l,r,g[pos[l]],x);x=work(l,posr[pos[l]],g[pos[l]],x);for(int i=pos[l]+1;i<=pos[r]-1;++i)x=sum[i][g[i]][x];x=work(posl[pos[r]],r,g[pos[r]],x);return x;
}
int main()
{freopen("training.in","r",stdin);freopen("training.out","w",stdout);n=read(),q=read();scanf("%s",s+1);block=pow(n,2.0/5.0);for(int i=1;i<=n;++i)a[i]=s[i]-'A'+1,pos[i]=(i-1)/block+1;for(int i=1;i<=pos[n];++i){posl[i]=(i-1)*block+1;posr[i]=min(i*block,n);g[i]=1;}for(int i=1;i<=3;++i)b[i]=i;do{tot++;p[tot][1]=b[1];p[tot][2]=b[2];p[tot][3]=b[3];vis[b[1]][b[2]][b[3]]=tot;for(int i=1;i<=3;++i)for(int j=1;j<=pos[n];++j)sum[j][tot][i]=work(posl[j],posr[j],tot,i);}while(next_permutation(b+1,b+4));while(q--){int opt=read(),l=read(),r=read();if(opt==0){scanf("%s %s",s1+1,s2+1);update(l,r,s1[1]-'A'+1,s2[1]-'A'+1); }else{scanf("%s",s1+1);printf("%c\n",ask(l,r,s1[1]-'A'+1)+'A'-1);}}return 0;
}