NOIP2023模拟16联测37 D. 小猫吃火龙果

联测37 D. 小猫吃火龙果"/>

NOIP2023模拟16联测37 D. 小猫吃火龙果

NOIP2023模拟16联测37 D. 小猫吃火龙果

文章目录

• NOIP2023模拟16联测37 D. 小猫吃火龙果
• • 题目大意
  • 思路
  • code

题目大意

有 n n n 个物品 A A A , B B B , C C C ， A A A 吃 B B B， B B B 吃 C C C， C C C 吃 A A A，有两种操作，给 [ l , r ] [ l , r ] [l,r] 的 x , y x , y x,y 互换，求出经过操作后得出什么。

n , m ≤ 2 × 1 0 5 n , m \le 2\times10^5 n,m≤2×105

思路

分块

维护一个状态 c i c_i ci​ 表示这个块的 A , B , C A , B , C A,B,C 分别变成了什么。

再维护一个 t o i d , x , y to_{id , x , y} toid,x,y​ 第 i d id id 块，状态为 x x x，把 y y y 带进去会带出来什么。

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define get_next(now , x) (now == (x + 1) % 3 ? x : now)
using namespace std;
const int N = 2e5 + 5;
int n , m , a[N] , block , to[N][6][3] , t[N];
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}};
inline int read () {char ch = getchar ();while (ch != 'A' && ch != 'B' && ch != 'C') ch = getchar ();return ch - 'A';
}
// inline int get_next (int now , int x) {
//     if (now == (x + 1) % 3) return x;
//     else return now;
// }
inline void updata (int id) {int l = id * block + 1 , r = min ((id + 1) * block , n);fu (i , 0 , 5) {fu (j , 0 , 2) {to[id][i][j] = j;fu (k , l , r) to[id][i][j] = get_next (to[id][i][j] , c[i][a[k]]);}}
}
inline void renew (int id) {int l = id * block + 1 , r = min ((id + 1) * block , n);fu (i , l , r) a[i] = c[t[id]][a[i]];t[id] = 0;
}
inline int rd () {int val = 0;char ch = getchar ();while (ch < '0' || ch > '9') ch = getchar ();while (ch >= '0' && ch <= '9') {val = val * 10 + (ch - '0');ch = getchar ();}return val;
}
int main () {freopen ("training.in" , "r" , stdin);freopen ("training.out" , "w" , stdout);int x , y , l , r , op , minr , id , type;n = rd () , m = rd ();fu (i , 1 , n) a[i] = read ();if(n>100)block = sqrt (n / 12);else block=sqrt(n);fu (i , 0 , (n + block - 1) / block) updata (i);while (m --) {op = rd () , l = rd () , r = rd ();if (op) {x = read ();id = (l - 1) / block;minr = min ((l - 1) / block * block + block , r);while (l <= minr) {x = get_next (x , c[t[id]][a[l]]);l ++;}while (l <= r - block + 1) {id = (l - 1) / block;x = to[id][t[id]][x];l += block;}id = (l - 1) / block;while (l <= r) {x = get_next (x , c[t[id]][a[l]]);l ++;}printf ("%c\n" , x + 'A');}else {x = read () , y = read ();if (x == y) continue;if (x > y) swap (x , y);id = (l - 1) / block;minr = min ((l - 1) / block * block + block , r);type = (x == 0 ? y == 1 ? 0 : 1 : 2);renew (id);while (l <= minr) {if (a[l] == x) a[l] = y;else if (a[l] == y) a[l] = x;l ++;}updata (id);while (l <= r- block + 1) {id = (l - 1) / block;t[id] = b[t[id]][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 ++;}updata (id);}}return 0;
}