NOIP2023 simulation 16 joint test 37 D. Kitten eats dragon fruit

NOIP2023 simulation 16 joint test 37 D. Kitten eats dragon fruit

Article directory

• NOIP2023 simulation 16 joint test 37 D. Kitten eats dragon fruit
• • The general idea of the topic
  • Ideas
  • code

The main idea of the title

have

n

n

n items

A

A

A,

B

B

B,

C

C

C,

A

A

A eat

B

B

B.

B

B

B eat

C

C

C.

C

C

C eat

A

A

A, there are two operations, given

[

l

,

r

]

[ l , r ]

[l,r] of

x

,

y

x , y

Swap x and y and find out what you get after the operation.

n

,

m

≤

2

×

1

0

5

n , m \le 2\times10^5

n,m≤2×105

Ideas

Block

maintain a state

c

i

c_i

ci? represents this block

A

,

B

,

C

A , B , C

What did A, B, and C become?

Maintain another one

t

o

i

d

,

x

,

y

to_{id , x , y}

toid,x,y? No.

i

d

ID

id block, status is

x

x

x, put

y

y

y What comes out when you bring it in.

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' & amp; & amp; ch != 'B' & amp; & amp; 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' & amp; & amp; 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)
        update(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\\
" , 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 + + ;
            }
            update(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 + + ;
            }
            update(id);
        }
    }
    return 0;
}