RT，WA on #11

可持久化trie

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+1,M=26;
int n,m,a[N],cnt=1,rt[N],S,sum[N];
struct node
{
    int son[2],fl,sz;
}tr[N*M];
void pushup(int rt)
{
    tr[rt].sz=tr[tr[rt].son[0]].sz+tr[tr[rt].son[1]].sz+tr[rt].fl;
}
void insert(int &rt,int lst,int x,int d)
{
    rt=++cnt;
    tr[rt]=tr[lst];
    if(d<0){
        tr[rt].sz++;
        tr[rt].fl++;
        return;
    }
    if(x>>d&1) insert(tr[rt].son[1],tr[lst].son[1],x,d-1);
    else insert(tr[rt].son[0],tr[lst].son[0],x,d-1);
    pushup(rt);
}
int query(int rt,int lst,int x,int d,int ss,int tt)
{
    if(d<0) return 0;
    int bit=!(x>>d&1);
    if(tr[tr[rt].son[bit]].sz>tr[tr[lst].son[bit]].sz)
        return (bit<<d)+query(tr[rt].son[bit],tr[lst].son[bit],x,d-1,ss,tt);
    else if(tr[tr[rt].son[!bit]].sz>tr[tr[lst].son[!bit]].sz)
        return (!bit<<d)+query(tr[rt].son[!bit],tr[lst].son[!bit],x,d-1,ss,tt);
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],S^=a[i],insert(rt[i],rt[i-1],S,M-1);
    for(int i=1,l,r,x;i<=m;i++){
        char c;
        cin>>c;
        if(c=='A'){
            cin>>x;
            S^=x;
            insert(rt[n+1],rt[n],S,M-1);
            n++;
        }
        else{
            cin>>l>>r>>x;
            if(r==1) cout<<(S^x)<<"\n";
            else cout<<(query(rt[r-1],rt[max(0,l-2)],x^S,M-1,l,r)^x^S)<<"\n";
        }
    }
}