最大异或和

给定一个非负整数序列 \(\{a\}\)，初始长度为 \(N\)。

有 \(M\) 个操作，有以下两种操作类型：

A x：添加操作，表示在序列末尾添加一个数 \(x\)，序列的长度 \(N\) 加 \(1\)。
Q l r x：询问操作，你需要找到一个位置 \(p\)，满足 \(l \le p \le r\)，使得：\(a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x\) 最大，输出最大值。

对于所有测试点，\(1\le N,M \le 3\times 10 ^ 5\)，\(0\leq a_i\leq 10 ^ 7\)。

分析：设 Si 表示前缀 i 个异或和，令 K=x⊕Sn，然后要在 [0,n−1] 中找到一个 p 使得 Sp⊕K 最大。

// 递归版
const int N=600010, len=23;
int n, m, s[N];
int ch[N*25][2], ver[N*25];
int root[N], idx;

void insert(int x,int y,int i,int k){
  ver[x] = i;
  if(k < 0) return;
  int c = s[i]>>k&1;
  ch[x][!c] = ch[y][!c];
  ch[x][c] = ++idx;
  insert(ch[x][c],ch[y][c],i,k-1);
}
int query(int x,int L,int v,int k){
  if(k < 0) return 0;
  int c = v>>k&1;
  if(ver[ch[x][!c]]>=L)
    return (1<<k)+query(ch[x][!c],L,v,k-1);
  else
    return query(ch[x][c],L,v,k-1);
}
int main(){
  int l,r,x,ans; char op;
  scanf("%d%d",&n,&m);
  ver[0] = -1;
  root[0] = ++idx;
  insert(root[0],0,0,len);
  for(int i=1; i <= n; i++){
    scanf("%d", &x);
    root[i] = ++idx;
    s[i] = s[i-1]^x;
    insert(root[i],root[i-1],i,len);
  }
  while(m--){
    scanf(" %c",&op);
    if(op == 'A'){
      scanf("%d",&x);
      root[++n] = ++idx;
      s[n] = s[n-1]^x;
      insert(root[n],root[n-1],n,len);
    }
    else{
      scanf("%d%d%d",&l,&r,&x);
      ans=query(root[r-1],l-1,s[n]^x,len);
      printf("%d\n", ans);
    }
  }
  return 0;
}