81pts WA#2 #11 求调

#include<iostream>
#include<algorithm>
const int sz=3e5+10;
int arr[sz<<1],root[sz<<1];
struct Trie{
    struct node{
        int cnt,son[2];
    }tree[sz<<8];
    int num=0;
    void insert(int p,int srt,int val){
        for(int i=23;i>=0;i--){
            int v=(val>>i)&1;
            if(tree[p].son[v]==0)tree[p].son[v]=++num;
            tree[p].son[v^1]=tree[srt].son[v^1];
            p=tree[p].son[v],srt=tree[srt].son[v];
            tree[p].cnt=tree[srt].cnt+1;
        }
    }
    int query(int urt,int vrt,int val){
        int ans=0;
        for(int i=23;i>=0;i--){
            int v=(val>>i)&1;
            if(tree[tree[vrt].son[v^1]].cnt!=tree[tree[urt].son[v^1]].cnt)
                ans+=1<<i,urt=tree[urt].son[v^1],vrt=tree[vrt].son[v^1];
            else urt=tree[urt].son[v],vrt=tree[vrt].son[v];
        }
        return ans;
    }
}trie;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n,q;
    std::cin>>n>>q;
    for(int i=1;i<=n;i++)
        std::cin>>arr[i],arr[i]^=arr[i-1];
    root[0]=++trie.num;
    for(int i=1;i<=n;i++)
        root[i]=++trie.num,trie.insert(root[i],root[i-1],arr[i]);
    while(q--){
        char op;
        std::cin>>op;
        if(op=='A'){
            ++n,std::cin>>arr[n];
            arr[n]^=arr[n-1];
            root[n]=++trie.num;
            trie.insert(root[n],root[n-1],arr[n]);
        }else{
            int l,r,x;
            std::cin>>l>>r>>x;
            l--,r--;
            if(l==0)std::cout<<trie.query(root[0],root[r],arr[n]^x)<<"\n";
            else std::cout<<trie.query(root[l-1],root[r],arr[n]^x)<<"\n";
        }
    }
    return 0;
}