最大异或和

感受

思路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 600000 + 10;
int root[maxn];
int XOR[maxn];
int tr[maxn * 32][2], cnt;
int n, m, x;
void init(){
    root[0] = ++cnt; int cur = cnt;
    for(int i = 30; i >= 0; i--){
        tr[cur][0] = ++cnt;
        cur = tr[cur][0];
    }
}
void add(int lastcur, int cur, int x){
    for(int i = 30; i >= 0; i--){
        int f = (x >> i) & 1;
        tr[cur][0] = tr[lastcur][0];
        tr[cur][1] = tr[lastcur][1];
        tr[cur][f] = ++cnt;
        cur = tr[cur][f]; lastcur = tr[lastcur][f];
    }
}
int query1(int lastcur, int cur, int x){
    int ans = 0;
    for(int i = 30; i >= 0; i--){
        int f = (x >> i) & 1; f ^= 1;
        if(tr[cur][f] != tr[lastcur][f]){
            ans += 1 << i;
        }
        else{
            f ^= 1;
        }
        cur = tr[cur][f]; lastcur = tr[lastcur][f];
    }
    return ans;
}
int query2(int cur, int x){
    int ans = 0;
    for(int i = 30; i >= 0; i--){
        int f = (x >> i) & 1; f ^= 1;
        if(!tr[cur][f]) f ^= 1;
        else ans += 1 << i;
        cur = tr[cur][f];
    }
    return ans;
}
int main(){
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= n; i++){
        scanf("%d", &XOR[i]);
        XOR[i] ^= XOR[i - 1];
        root[i] = ++cnt;
        add(root[i - 1], root[i], XOR[i]);
    }
    string tmp; int l, r, x;
    for(int i = 1; i <= m; i++){
        cin >> tmp;
        if(tmp[0] == 'A'){
            n++;
            scanf("%d", &XOR[n]);
            XOR[n] ^= XOR[n - 1];
            root[n] = ++cnt;
            add(root[n - 1], root[n], XOR[n]);
        }
        else{
            scanf("%d%d%d", &l, &r, &x);
            if(l >= 2) printf("%d\n", query1(root[l - 2], root[r - 1], x ^ XOR[n]));
            else printf("%d\n", query2(root[r - 1], x ^ XOR[n]));
            //XOR[l-1、l、...、r-1] ^ XOR[n]
        }
    }
    return 0;
}