最大异或和

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

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

  1. A x：添加操作，表示在序列末尾添加一个数 xx，序列的长度 NN 加 11。
  2. Q l r x：询问操作，你需要找到一个位置 pp，满足 l≤p≤rl \le p \le r，使得：a[p]⊕a[p+1]⊕...⊕a[N]⊕xa[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x 最大，输出最大值。
  • 对于所有测试点，1≤N,M≤3×1051\le N,M \le 3\times 10 ^ 5，0≤ai≤1070\leq a_i\leq 10 ^ 7。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 递归版
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;
}