2023NOIP A层联测28 T4 小猫吃火龙果
分块题,跟赛时的一个倍增部分分做法很像。
思路
如果没有动态操作,可以设 \(dp[i][T][k]\) 为:在 \(i\) 时为 \(T(T\in{\{A,B,C}\})\),算上 \(i\) 向前 \(2^k\) 步得到的字符。
转移:
\[dp[i][T][k]=dp[i+2^k-1][dp[i][T][k-1]][k-1]
\]
特别的,当 \(k=0\) 时,\(dp[i][T][0]\) 需要特别赋值。
这个做法提供了一个很好的想法,可以钦定到一个点时的字符,向后跳若干步时直接得到该步的答案。
加上动态操作,可以分块去做。
对于每一个块,我们把钦定的字符后,块内的点的每 6 种变化情况所造成的不同的答案都记录下来。
对于每一个更改操作,整块直接更改该块的变化情况编号;零散块暴力更改后,再次暴力维护块内的各项数据。
对于每一个查询,零散块暴力跳,整块直接跳一块答案,每次可以按照类似于 dp 做法的方式维护答案。
CODE
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,m,block;
int to[maxn][6][3],t[2000];
int c[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
int b[6][3]={{2,5,1},{3,4,0},{0,3,4},{1,2,5},{5,1,2},{4,0,3}};
char a[maxn];
set< pair<int,int> >s;
int gt(int now,int x){return now==(x+1)%3?x:now;}
void renew(int id)
{
int l=id*block+1,r=min(l+block-1,n);
for(int i=l;i<=r;i++) a[i]=c[t[id]][a[i]-'A']+'A';
t[id]=0;
}
void updata(int id)
{
int l=id*block+1,r=min(l+block-1,n);
for(int x=0;x<6;x++)
{
for(int y=0;y<3;y++)
{
to[id][x][y]=y;
for(int i=l;i<=r;i++) to[id][x][y]=gt(to[id][x][y],c[x][a[i]-'A']);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
cin>>a+1;
block=sqrt((n+17)/18);
for(int i=0;i<=(n+block-1)/block;i++) updata(i);
for(int i=1;i<=m;i++)
{
int op,l,r;
char t1,t2;
cin>>op>>l>>r>>t1;
if(op==0)
{
cin>>t2;
if(t1==t2) continue;
if(t1>t2) swap(t1,t2);
int tp=(t1=='A'?t2=='B'?0:1:2);
int idl=(l-1)/block;
int idr=(r-1)/block;
if(idl==idr)
{
renew(idl);
for(int j=l;j<=r;j++)
{
if(a[j]==t1) a[j]=t2;
else if(a[j]==t2) a[j]=t1;
}
updata(idl);
}
else
{
renew(idl);
for(int j=l;j<=idl*block+block;j++)
{
if(a[j]==t1) a[j]=t2;
else if(a[j]==t2) a[j]=t1;
}
updata(idl);
for(int j=idl+1;j<=idr-1;j++) t[j]=b[t[j]][tp];
renew(idr);
for(int j=idr*block+1;j<=r;j++)
{
if(a[j]==t1) a[j]=t2;
else if(a[j]==t2) a[j]=t1;
}
updata(idr);
}
}
else
{
int idl=(l-1)/block;
int idr=(r-1)/block;
t1-='A';
if(idl==idr)
for(int j=l;j<=r;j++) t1=gt(t1,c[t[idl]][a[j]-'A']);
else
{
for(int j=l;j<=idl*block+block;j++) t1=gt(t1,c[t[idl]][a[j]-'A']);
for(int j=idl+1;j<=idr-1;j++) t1=to[j][t[j]][t1];
for(int j=idr*block+1;j<=r;j++) t1=gt(t1,c[t[idr]][a[j]-'A']);
}
cout<<(char)(t1+'A')<<"\n";
}
}
}