目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

State

\(0<=a[i]<=10^{7}\)

\(N,\; M<=3*10^{5}\)

Input

5  5
2  6 4 3 6
A 1 
Q 3 5 4 
A 4
Q 5 7 0 
Q 3 6 6 

Output

4
5
6

Solution

\(a[p]⊕a[p+1]……⊕a[N]⊕x \; = sum[N]⊕sum[p - 1]⊕x\)

也就是说再区间 \([L,\; R]\) 中找到一个位置 \(p\) ，使得 \(sum[N]⊕x\) 异或其前缀最小

Code

const int N = 6e5 + 5;

    ll n, m, _;
    int i, j, k;
    ll a[N];
    int ch[N * 24][2], sz[N * 24];
    int tot = 0, root[N];

void ins(int &x, int y, int c)
{
    x = ++ tot; 
    int nx = x, ny = y;
    for(int i = 24; ~ i; i --){
        int id = (c >> i) & 1;
        ch[nx][0] = ch[ny][0];
        ch[nx][1] = ch[ny][1];
        ch[nx][id] = ++ tot;
        nx = ch[nx][id];
        ny = ch[ny][id];
        sz[nx] = sz[ny] + 1;
    }
}

int query(int x, int y, int c)
{
    int ans = 0;
    for(int i = 24; ~ i; i --){
        int id = (c >> i) & 1;
        if(sz[ch[y][!id]] - sz[ch[x][!id]] > 0){
            ans |= (1 << i);
            x = ch[x][!id];
            y = ch[y][!id];
        }
        else{
            x = ch[x][id];
            y = ch[y][id];
        }
    }
    return ans;
}

signed main()
{
    //IOS;
    while(~ sdd(n, m)){
        ins(root[0], root[0], 0);
        rep(i, 1, n){
            sd(a[i]);
            a[i] ^= a[i - 1];
            ins(root[i], root[i - 1], a[i]);
        }
        rep(i, 1, m){
            char opt;
            int x, l, r;
            scanf(" %c", &opt);
            if(opt == ‘Q‘){
                sddd(l, r, x);
                int ans = query(root[l - 2], root[r - 1], a[n] ^ x);
                pd(ans);
            } 
            else if(opt == ‘A‘){
                sd(x);
                a[++ n] = x ^ a[n];
                ins(root[n], root[n - 1], a[n]);
            }
        }
    }
    return 0;
}