最大异或和

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

有 $M$ 个操作，有以下两种操作类型：

  1. A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $N$ 加 $1$。
  2. 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;
}