「BZOJ3261」最大异或和

Description

给定一个非负整数序列{a}\{a\},初始长度为NN
有M个操作,有以下两种操作类型:

  • A x:添加操作,表示在序列末尾添加一个数xx,序列的长度N+1N+1
  • Q l r x:询问操作,你需要找到一个位置pp,满足lprl \le p \le r,使得: a[p]a[p+1]...a[N]x a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x 最大,输出最大是多少。

Input

第一行包含两个整数 N,MN,M,含义如问题描述所示。
第二行包含 NN个非负整数,表示初始的序列AA
接下来 MM行,每行描述一个操作,格式如题面所述。

Output

假设询问操作有 TT 个,则输出应该有 TT 行,每行一个整数表示询问的答案。

Sample Input

1
2
3
4
5
6
7
5  5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6

Sample Output

1
2
3
4
5
6

HINT

对于测试点 121-2N,M5N,M \le 5
对于测试点 373-7N,M80000N,M \le 80000
对于测试点 8108-10N,M300000N,M \le 300000
其中测试点 1,3,5,7,91, 3, 5, 7, 9保证没有修改操作。
0a[i]1070 \le a[i] \le 10^7

Solution

可持久化trie树的模板题。
可持久化类似于主席树的思想。
注意每个标号要i+1i+1,来避免错误。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 310000;
int n, m;
int a[N], rt[N*3], siz[N*25*2];

int ch[N*25*2][2], tot;
void ins(int pre, int &o, int val) {
o = ++tot;
int p = o;
for(int i = 25; ~i; --i) {
int nxt = (val >> i) & 1;
ch[p][nxt] = ++tot;
ch[p][nxt ^ 1] = ch[pre][nxt ^ 1];
p = ch[p][nxt];
pre = ch[pre][nxt];
siz[p] = siz[pre] + 1;
}
}
int query(int pre, int o, int val) {
int res = 0;
for(int i = 25; ~i; --i) {
int nxt = (val >> i) & 1;
if(siz[ch[o][nxt ^ 1]] - siz[ch[pre][nxt ^ 1]] > 0) {
res += (1 << i);
o = ch[o][nxt ^ 1];
pre = ch[pre][nxt ^ 1];
} else {
o = ch[o][nxt];
pre = ch[pre][nxt];
}
}
return res;
}
int sum[N*3];
char op[8];
int main() {
n = read(), m = read();
ins(rt[0], rt[0 + 1], 0);
for(int i = 1; i <= n; ++i) {
a[i] = read();
sum[i + 1] = sum[i] ^ a[i];
ins(rt[i], rt[i + 1], sum[i + 1]);
}
int num = n + 1;
for(int i = 1; i <= m; ++i) {
scanf("%s", op);
if(op[0] == 'A') {
int x = read();
++num;
sum[num] = sum[num - 1] ^ x;
ins(rt[num - 1], rt[num], sum[num]);
} else {
int l = read(), r = read(), x = read();
++l, ++r;
writeln(query(rt[l - 2], rt[r - 1], x ^ sum[num]));
}
}
return 0;
}