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

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

题目大意

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

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

思路

分块

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

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

code

#include 
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104