可持久化Trie树和可持久化线段树差不多。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=15e6+10;
const int M=6e5+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
} 
struct Trie{int c,son[2];}t[N];int root[N],cnt;
void build(int now,int last,int d)
{
    now=++cnt;t[now]=t[last];
    for(int i=24;~i;i--)
    {
        int c=d>>i&1;
        t[now].son[c]=++cnt;
        now=t[now].son[c];
        last=t[last].son[c];
        t[now]=t[last];
        ++t[now].c;//记录路径。
    }
}
int ans;
void query(int now,int last,int d)
{
    for(int i=24;~i;i--)
    {
        int c=d>>i&1;
        /*在[l,r]有一个或多个字符串,满足之前的要求(每一位上都符合0,1),且满足当前的要求,才会判断为true,也就是这个异或前缀和字符串一定存在于[l,r]之中。*/
        if(t[t[now].son[c^1]].c-t[t[last].son[c^1]].c)
        {
            ans+=1<<i;
            now=t[now].son[c^1],last=t[last].son[c^1];
        }
        else now=t[now].son[c],last=t[last].son[c];
    }
}
int main()
{
    int n,m;qr(n),qr(m);
    int sum=0;root[0]=cnt+1;build(root[0],root[0],sum);
    for(int i=1,x;i<=n;i++)
    {   
        qr(x);sum^=x;root[i]=cnt+1;build(root[i],root[i-1],sum);
    }   
    for(int i=1,x,l,r;i<=m;i++)
    {
        char op[3];scanf("%s",op);
        if(op[0]=='A')qr(x),sum^=x,root[++n]=cnt+1,build(root[n],root[n-1],sum);
        else qr(l),qr(r),qr(x),ans=0,query(root[r-1],root[l-2],sum^x),qw(ans),puts("");//s[l-1]~s[r-1]可用 
    }
    return 0;
}