最大异或和（可持久化01trie）

最大异或和

题意：转化后的题意是有一种操作+一种询问：
1. 操作：在序列末尾插入一个数
2. 询问：给定 $l,r,x$l,r,x，求区间 $l,r$l,r中与 $x$x异或能得到的最大异或值（转化后的题意）

思路：题意都被转化成这样了。。。应该就没啥难度了

1. 用类似主席树的方式构建可持久化 $01trie$01trie
2. 然后还是简单的贪心跑 $01trie$01trie
3. 最后小心给定的 $l,r$l,r都等于 $1$1的情况，特判一下即可（还没有想好如何不特判）

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 6e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int N, M;
int root[maxn], son[maxn<<5][2], sz[maxn<<5], tot;

void insert(int p, int i, int pre, int &now) {
    sz[now=++tot]=sz[pre]+1;
    if(i<0) return;
    int s=p>>i&1;
    son[now][!s]=son[pre][!s];
    insert(p,i-1,son[pre][s],son[now][s]);
}

int query(int x, int y, int p, int i) {
    if(i<0) return 0;
    int s=p>>i&1;
    if(sz[son[y][!s]]-sz[son[x][!s]]>0) return (1<<i)+query(son[x][!s],son[y][!s],p,i-1);
    return query(son[x][s],son[y][s],p,i-1);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    N=read(), M=read();
    int pre=0;
    insert(0,30,root[0],root[0]);
    for(int i=1; i<=N; ++i) insert(pre^=read(),30,root[i-1],root[i]);
    while(M--) {
        char s[2]; scanf("%s", s);
        if(s[0]=='A') insert(pre^=read(),30,root[N],root[N+1]), ++N;
        else {
            int l=read()-1, r=read()-1, x=pre^read();
            if(l==r&&l==0) printf("%d\n", x);
            else printf("%d\n", query(root[max(0,l-1)],root[r],x,30));
        }
    }
}