最大异或和

最大异或和

关键

1.开头需要加个0
2.l和r这里需要减去1

代码

#include <bits/stdc++.h>
using namespace std;
const int M=6e5+5;

int rot[M],cnt[M*24],ch[M*24][2],tot;
int sum[M];
void insert(int L,int R,int i,int x) {
    if(i<0)return ;
    int v=x>>i&1;
    ch[R][v^1]=ch[L][v^1];//直接继承
    ch[R][v]=++tot;//新开一个点
    cnt[ch[R][v]]=cnt[ch[L][v]]+1;
    insert(ch[L][v],ch[R][v],i-1,x);
}

int query(int L,int R,int i,int x) {
    if(i<0)return 0;
    int v=x>>i&1;
    if(cnt[ch[R][v^1]]>cnt[ch[L][v^1]])return (1<<i)+query(ch[L][v^1],ch[R][v^1],i-1,x);
    return query(ch[L][v],ch[R][v],i-1,x);
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    rot[0]=++tot;
    insert(0,rot[0],23,0);//加上一个0，也就是全部选择自己的情况，这个是需要注意的
    for(int i=1;i<=n;i++) {
        int x;cin>>x;
        sum[i]=sum[i-1]^x;
        rot[i]=++tot;
        insert(rot[i-1],rot[i],23,sum[i]);
    }
    while(m--) {
        char ch;cin>>ch;
        if(ch=='A') {
            int x;cin>>x;
            n++;
            sum[n]=sum[n-1]^x;
            rot[n]=++tot;
            insert(rot[n-1],rot[n],23,sum[n]);
        }
        else {
            int l,r,x;
            cin>>l>>r>>x;
            l--,r--;//异或和的性质,从前面选择就可以了
            if(l==0)cout<<query(0,rot[r],23,x^sum[n])<<'\n';//这里是一个坑点
            else cout<<query(rot[l-1],rot[r],23,x^sum[n])<<'\n';//直接找就可以了
        }
    }
    return 0;
}