最大异或和

题意

给你一个序列,让你进行次操作。操作有如下两种：1.在序列末尾添加一个数。2.求以到内的任意位置为起始，以为结尾，是的这个子序列异或和最大。

分析

可以看出这是一个可持久化Tire树，首先利用前缀和转化问题，将查询操作转化为求。如果查询没有区间限制，那么就是一个Tire树就可以。但有了区间限制就无法直接用Tire树求解。考虑用可持久化，每次询问区间时即为相当于用第个版本的树-第个版本的树得到区间的树。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e8+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m;
int root[N],son[N][2],tot,rtn,sum[N];
int base[32];
char opt[5];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void add(int x)
{
    root[++rtn]=tot+1;
    int last=root[rtn-1];
    for(int i=23;~i; i--)
    {
      sum[++tot]=sum[last]+1;
      bool b=x&base[i];
      son[tot][b]=tot+1,son[tot][!b]=son[last][!b];
      last=son[last][b];
    }
    sum[++tot]=sum[last]+1;
}

int query(int lt,int rt,int x)
{
    if(lt>rt) return 0;
    lt=root[lt-1];
    rt=root[rt];
    int ans=0;
    for(int i=23;~i; i--)
    {
      bool b=x&base[i];
      if(sum[son[rt][!b]]-sum[son[lt][!b]])
        ans+=base[i],lt=son[lt][!b],rt=son[rt][!b];
      else
        lt=son[lt][b],rt=son[rt][b];
    }
    return ans;
}

int main()
{
    n=read();m=read();
    base[0]=1;
    for(int i=1;i<=23;i++) base[i]=base[i-1]<<1;
    add(0);
    int now=0;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        add(now^=x);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",opt);
        if(opt[0]=='A')
        {
            int x=read();
            add(now^=x);
        }
        else
        {
            int l=read(),r=read(),x=read();
            printf("%d\n",query(l,r,now^x));
        }
    }
    return 0;
}