P4735 最大异或和（可持久化字典树 ？ 主席树）

异或满足可减性，所以可以维护前缀和，然后  
      a[p] xor a[p + 1] xor ... xor a[n] xor = s[p - 1] xor s[n] xor
然后就只要维护s[]。添加很好维护，重点是如何查询
此时查询转变为：val = s[n] xor x，求一个p∈[l - 1, r - 1]使得s[p] xor val最大
可以构建一颗可持久化Trie，第i个版本为插入了s[i]后的Trie树。
每次查询，从根节点开始，贪心地选与这一位相反的值。
此外，还有一个l−1≤p≤r−1的限制。
先考虑p≤r−1，查询第r−1个版本的Trie即可，因为此时不可能访问到r-1r−1之后的ss。 再考虑l−1≤p，对每个节点维护一个latest值，表示子树中所有ss值的下标的最大值。这样，在查询时只访问latest≥l−1的节点就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 5;
struct Node {
  int son[2], cnt;
}trie[maxn * 30];
int n, m, tot, ans, rt[maxn];
char opt[2];
void insert(int &x, int y, int d, int num) {
  x = ++tot;
  trie[x] = trie[y];
  trie[x].cnt++;
  if (d < 0) {
    return ;
  }
  int t = num & (1 << d) ? 1 : 0;
  insert(trie[x].son[t], trie[y].son[t], d - 1, num);
}
void query(int x, int y, int d, int num) {
  if (d < 0) {
    return ;
  }
  int t = num & (1 << d) ? 1 : 0;
  int dl = trie[trie[x].son[t ^ 1]].cnt;
  int dr = trie[trie[y].son[t ^ 1]].cnt;
  if (dr - dl) {
    ans |= (1<< d);
    query(trie[x].son[t ^ 1], trie[y].son[t ^ 1], d - 1, num);
  } else {
    query(trie[x].son[t], trie[y].son[t], d - 1, num);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  n++;
  int sum = 0, l, r, x;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    sum ^= x;
    insert(rt[i], rt[i - 1], 24, sum);
  }
  while (m--) {
    scanf("%s", opt);
    if (opt[0] == 'A') {
      scanf("%d", &x);
      sum ^= x;
      insert(rt[++n], rt[n], 24, sum);
    } else {
      scanf("%d%d%d", &l, &r, &x);
      x ^= sum; ans = 0;
      l++; r++;
      query(rt[l - 2], rt[r - 1], 24, x);
      printf("%d\n", ans);
    }
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 5;
struct Node {
  int son[2], cnt;
}trie[maxn * 30];
int n, m, tot, ans, rt[maxn];
int opt[2];
void insert(int &nowp, int last, int d, int num) {
  nowp = ++tot;
  trie[nowp] = trie[last];
  trie[nowp].cnt++;
  if (d < 0) {
    return;
  }
  int t = num & (1 << d) ? 1 : 0;
  insert(trie[nowp].son[t], trie[last].son[t], d - 1, num);
}
void query(int nowp, int last, int d, int num) {
  if (d < 0) {
    return ;
  }
  int t = num & (1 << d) ? 1 : 0;
  int dr = trie[trie[nowp].son[t ^ 1]].cnt;
  int dl = trie[trie[last].son[t ^ 1]].cnt;
  if (dr - dl) {
    ans |= (1 << d);
    query(trie[nowp].son[t ^ 1], trie[last].son[t ^ 1], d - 1, num);
  } else {
    query(trie[nowp].son[t], trie[last].son[t], d - 1, num);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  int x, l, r;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    insert(rt[i], rt[i - 1], 30, x);
  }
  while (m--) {
    scanf("%d%d%d", &x, &l, &r); ans = 0;
    query(rt[r + 1], rt[l], 30, x);
    printf("%d\n", ans);
  }
  return 0;
}