灵芝住房和城乡建设局局网站,智能制造工程,郑州个人网站制作公司,二级网站建设管理制度给你一个长为 n n n 的序列#xff0c;每个位置是 A , B , C A,B,C A,B,C 三个中的一个物品。 A A A 吃 B B B#xff0c; B B B 吃 C C C#xff0c; C C C 吃 A A A。
现在有 m m m 次操作#xff0c;每次操作有两种#xff1a; 区间修改#xff1a;给出 l , r…给你一个长为 n n n 的序列每个位置是 A , B , C A,B,C A,B,C 三个中的一个物品。 A A A 吃 B B B B B B 吃 C C C C C C 吃 A A A。
现在有 m m m 次操作每次操作有两种 区间修改给出 l , r , x , y l,r,x,y l,r,x,y表示将 [ l , r ] [l,r] [l,r] 区间内所有的 x x x 改成 y y y所有的 y y y 改成 x x x两种修改同时进行。 区间询问给出 l , r , x l,r,x l,r,x现在沙奈朵一开始手上拿着的是一个 x x x 物品。沙奈朵从序列的 l l l 位置开始一路走到 r r r 位置结束每次他需要对比他手上的物品和当前序列位置的物品如果手上的物品可以吃掉当前序列位置的物品则手上的物品不变否则手上的物品变成当前序列位置的物品。区间询问操作对序列没有任何修改。 求走完了 [ l , r ] [l,r] [l,r] 这个区间后沙奈朵手上的物品是什么。对区间 [ l , r ] [l,r] [l,r] 中的每一个位置包括端点都需要执行操作。 n , m ≤ 2 × 1 0 5 n,m\le2\times10^5 n,m≤2×105 考虑用分块维护。由于有交换两种字母的操作那么对于每个就要维护三个字母所有置换 6 6 6 种。将 A B C , A C B , B A C , B C A , C A B , C B A ABC,ACB,BAC,BCA,CAB,CBA ABC,ACB,BAC,BCA,CAB,CBA 分别表示为 0 , 1 , 2 , 3 , 4 , 5 0,1,2,3,4,5 0,1,2,3,4,5将修改操作交换 A B , A C , B C AB,AC,BC AB,AC,BC 分别表示为 0 , 1 , 2 0,1,2 0,1,2记块长为 B B B
设 c x , y c_{x,y} cx,y 表示字母是 y y y经过置换 x x x 会变成的字母。 b x , y b_{x,y} bx,y 表示经过修改 y y y 后置换 x x x 会变成的置换。 t o i d , x , y to_{id,x,y} toid,x,y 表示第 i d id id 个块置换为 x x x开始是字母 y y y走完这个块后所变成的字母。 t i d t_{id} tid 表示第 i d id id 个块的置换。
显然 c , b c,b c,b 可以打表 t o to to 可以 O ( B ) O(B) O(B) 求出。
下面考虑维护。
修改。对于散块先更新所在的块的真实值然后直接修改再 O ( B ) O(B) O(B) 求出 t o i d to_{id} toid对于整块就用 b b b 更改 t i d t_{id} tid 即可。查询。对于散块就直接暴力比对对于整块就用之前求出的 t o to to 更新答案。
时间复杂度 O ( n n ) O(n\sqrt n) O(nn )但是由于修改时对于散块的求 t o to to 的时间复杂度实际上要带上 18 18 18 的常数所以块长取 ⌈ n 18 ⌉ \sqrt{\lceil\frac n{18}\rceil} ⌈18n⌉ 比较合适。
具体实现参照代码
#includebits/stdc.h
#define getnxt(now,x) (now(x1)%3?x:now)
using namespace std;
const int N2e51;
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 lid*block1,rmin(id*blockblock,n);for(int il;ir;i) a[i]c[t[id]][a[i]-65]65;t[id]0;
}
void update(int id)
{int lid*block1,rmin(id*blockblock,n);for(int x0;x6;x){for(int y0;y3;y){to[id][x][y]y;for(int il;ir;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);cinnm(a1);blocksqrt((n17)/18);for(int i0;i(nblock-1)/block;i) update(i);for(int i1,op,l,r;im;i){char x,y;cinoplrx;if(op){int minrmin((l-1)/block*blockblock,r),id(l-1)/block;x-65;while(lminr){xgetnxt(x,c[t[id]][a[l]-65]);l;}while(r-l1block){id(l-1)/block;xto[id][t[id]][x];lblock;}id(l-1)/block;while(lr){xgetnxt(x,c[t[id]][a[l]-65]);l;}coutchar(x65)\n;}else{ciny;if(xy) continue;if(xy) swap(x,y);int type(xA?yB?0:1:2);int minrmin((l-1)/block*blockblock,r),id(l-1)/block;renew(id);while(lminr){if(a[l]x) a[l]y;else if(a[l]y) a[l]x;l;}update(id);while(r-l1block){t[(l-1)/block]b[t[(l-1)/block]][type];lblock;}renew(id(l-1)/block);while(lr){if(a[l]x) a[l]y;else if(a[l]y) a[l]x;l;}update(id);}}
}
