Description
给定一个初始长度为 \(N\) 的非负整数序列 \(\{A\}\) 。有 \(M\) 个操作，支持：
- \(A~x\) ：添加操作，表示在序列末尾添加一个数 \(x\) ，序列的长度 \(N+1\) 。
- \(Q~l~r~x\) ：询问操作，求 \[\max_{l\leq p\leq r}A_p\oplus A_{p+1}\oplus\cdots\oplus A_N\oplus x\]
\(1\leq N,M\leq 300000,0\leq A_i\leq 10^7\)
Solution
不妨记 \(A_i\) 的前缀异或和为 \(B_i\) ，显然题目转化为 \[\max_{l\leq p\leq r}B_{p-1}\oplus B_N\oplus x\]
我们不妨用类似主席树的思路，我们建一棵 \(B_i\) 的 \(Trie\) ，并且将它持久化，然后贪心的选择。显然是可行的。
值得注意的是由于异或的前缀和，并且又因为差分，查询时的区间应该为 \([l-2,r-1]\) ，为了防止越界，可以先插入个 \(0\) 进 \(Trie\) 。
Code
//It is made by Awson on 2018.3.16#include#define LL long long#define dob complex #define Abs(a) ((a) < 0 ? (-(a)) : (a))#define Max(a, b) ((a) > (b) ? (a) : (b))#define Min(a, b) ((a) < (b) ? (a) : (b))#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))#define writeln(x) (write(x), putchar('\n'))#define lowbit(x) ((x)&(-(x)))using namespace std;const int N = 300000;void read(int &x) { char ch; bool flag = 0; for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar()); for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar()); x *= 1-2*flag;}void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }int n, m, bin[30], a, b, t, A[30], l, r; char ch[5];struct Trie { int root[(N<<1)+5], ch[N*50+5][2], key[N*50+5], pos; int cpynode(int o) {++pos; ch[pos][0] = ch[o][0], ch[pos][1] = ch[o][1], key[pos] = key[o]; return pos; } void insert(int &o, int *A) { int u = o = cpynode(o); ++key[u]; for (int i = 25; i >= 1; i--) { ch[u][A[i]] = cpynode(ch[u][A[i]]); u = ch[u][A[i]], ++key[u]; } } int query(int a, int b, int *A) { int ans = 0; for (int i = 25; i >= 1; i--) { if (key[ch[b][A[i]^1]]-key[ch[a][A[i]^1]] > 0) ans += bin[i-1], a = ch[a][A[i]^1], b = ch[b][A[i]^1]; else a = ch[a][A[i]], b = ch[b][A[i]]; } return ans; }}T;void work() { read(n), read(m); bin[0] = 1; for (int i = 1; i <= 25; i++) bin[i] = (bin[i-1]<<1); T.insert(T.root[1], A); ++n; for (int i = 2; i <= n; i++) { read(a), b ^= a, t = b; for (int j = 1; j <= 25; j++) A[j] = t%2, t /= 2; T.insert(T.root[i] = T.root[i-1], A); } while (m--) { scanf("%s", ch); if (ch[0] == 'A') { ++n; read(a), b ^= a, t = b; for (int j = 1; j <= 25; j++) A[j] = t%2, t /= 2; T.insert(T.root[n] = T.root[n-1], A); }else { read(l), read(r), read(t); t ^= b; for (int j = 1; j <= 25; j++) A[j] = t%2, t /= 2; writeln(T.query(T.root[l-1], T.root[r], A)); } }}int main() { work(); return 0;}