2023NOIP A层联测28-小猫吃火龙果

给你一个长为 $n$ 的序列，每个位置是 $A,B,C$ 三个中的一个物品。

$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。

现在有 $m$ 次操作，每次操作有两种：

1. 区间修改：给出 $l,r,x,y$，表示将 $[l,r]$ 区间内所有的 $x$ 改成 $y$，所有的 $y$ 改成 $x$（两种修改同时进行）。

2. 区间询问：给出 $l,r,x$，现在沙奈朵一开始手上拿着的是一个 $x$ 物品。沙奈朵从序列的 $l$ 位置开始一路走到 $r$ 位置结束，每次他需要对比他手上的物品和当前序列位置的物品，如果手上的物品可以吃掉当前序列位置的物品，则手上的物品不变，否则手上的物品变成当前序列位置的物品。区间询问操作对序列没有任何修改。 求走完了 $[l,r]$ 这个区间后，沙奈朵手上的物品是什么。对区间 $[l,r]$ 中的每一个位置，包括端点，都需要执行操作。

$n,m\le 2\times 10^5$

---

考虑用分块维护。由于有交换两种字母的操作，那么对于每个就要维护三个字母所有置换（$6$ 种）。将 $ABC,ACB,BAC,BCA,CAB,CBA$ 分别表示为 $0,1,2,3,4,5$；将修改操作交换 $AB,AC,BC$ 分别表示为 $0,1,2$；记块长为 $B$

设
$c_{x,y}$ 表示字母是 $y$，经过置换 $x$ 会变成的字母。
$b_{x,y}$ 表示经过修改 $y$ 后，置换 $x$ 会变成的置换。
$t{o}_{id,x,y}$ 表示第 $id$ 个块置换为 $x$，开始是字母 $y$，走完这个块后所变成的字母。
$t_{id}$ 表示第 $id$ 个块的置换。

显然 $c,b$ 可以打表，$to$ 可以 $O(B)$ 求出。

下面考虑维护。

• 修改。对于散块先更新所在的块的真实值，然后直接修改，再 $O(B)$ 求出 $t{o}_{id}$；对于整块就用 $b$ 更改 $t_{id}$ 即可。
• 查询。对于散块就直接暴力比对；对于整块就用之前求出的 $to$ 更新答案。

时间复杂度 $O(n\sqrt{n})$，但是由于修改时对于散块的求 $to$ 的时间复杂度实际上要带上 $18$ 的常数，所以块长取 $\sqrt{\lceil \frac{n}{18}\rceil }$ 比较合适。

具体实现参照代码：

#include<bits/stdc++.h>
#define getnxt(now,x) (now==(x+1)%3?x:now)
using namespace std;
const int N=2e5+1;
int n,m,block,to[2000][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[N];
void renew(int id)
{int l=id*block+1,r=min(id*block+block,n);for(int i=l;i<=r;i++) a[i]=c[t[id]][a[i]-65]+65;t[id]=0;
}
void update(int id)
{int l=id*block+1,r=min(id*block+block,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]=getnxt(to[id][x][y],c[x][a[i]-65]);}}}
}
int main()
{freopen("training.in","r",stdin);freopen("training.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n>>m>>(a+1);block=sqrt((n+17)/18);for(int i=0;i<=(n+block-1)/block;i++) update(i);for(int i=1,op,l,r;i<=m;i++){char x,y;cin>>op>>l>>r>>x;if(op){int minr=min((l-1)/block*block+block,r),id=(l-1)/block;x-=65;while(l<=minr){x=getnxt(x,c[t[id]][a[l]-65]);l++;}while(r-l+1>=block){id=(l-1)/block;x=to[id][t[id]][x];l+=block;}id=(l-1)/block;while(l<=r){x=getnxt(x,c[t[id]][a[l]-65]);l++;}cout<<char(x+65)<<"\n";}else{cin>>y;if(x==y) continue;if(x>y) swap(x,y);int type=(x=='A'?y=='B'?0:1:2);int minr=min((l-1)/block*block+block,r),id=(l-1)/block;renew(id);while(l<=minr){if(a[l]==x) a[l]=y;else if(a[l]==y) a[l]=x;l++;}update(id);while(r-l+1>=block){t[(l-1)/block]=b[t[(l-1)/block]][type];l+=block;}renew(id=(l-1)/block);while(l<=r){if(a[l]==x) a[l]=y;else if(a[l]==y) a[l]=x;l++;}update(id);}}
}