最大异或和

题目描述

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

有$M$个操作,有以下两种操作类型:

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

$N,M \le 300000$
$0≤a[i]≤10^7$

代码

一直TTT的,然后忍不住去找了标程,发现方法没错,就是常数…简直叹为观止
现在总算是可以了

令$s[i] = a[1] \ xor \ a[2] \ xor \ … \ xor \ a[i]$

则有$a[i] \ xor \ a[i + 1] \ xor \ … \ xor \ a[N] = s[N] \ xor \ s[i - 1]$

所以,就以$s[N] \ xor \ x$为标准, 在$p \in [l - 1, r - 1]$的范围内普通的求最大异或值就好

为了方便限制范围,我们增加newr数组存储每个点所属的数字下标,不允许搜索到$newr[i] < l - 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
inline void insert(int i, int p, int q){
int k = 23;
while(k >= 0){
c = s[i] >> k & 1; -- k;
//之前错写成c = s[i] & (1 << k) 了,还自以为没错..
son[q][c ^ 1] = son[p][c ^ 1];
son[q][c] = ++ tot;
newr[tot] = i;
p = son[p][c], q = son[q][c];
//因为编号为0的节点左右皆为0所以怎样都没关系
}
}

int ask(int now, int val, int limit){
int k = 23;
while(k >= 0){
c = val >> k & 1; -- k;
if(newr[son[now][c ^ 1]] >= limit) now = son[now][c ^ 1];
else now = son[now][c];
}
return s[newr[now]] ^ val;
}

int main() {
n = read(), m = read();
newr[0] = -1, root[0] = ++tot;
insert(0, 23, 0, root[0]);
//一定要建立0号根节点啊
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] ^ read(), root[i] = ++ tot;
insert(i, root[i - 1], root[i]);
}
for (int i = 1; i <= m; i++) {
scanf("%s", op);
if (op[0] == 'A') {
root[++ n] = ++ tot, s[n] = s[n - 1] ^ read();
insert(n, root[n - 1], root[n]);
}
else {
l = read(), r = read(), x = read();
printf("%d\n", ask(root[r - 1], x ^ s[n], l - 1));
//[l - 1, r - 1]
}
}
return 0;
}

日常

luogu上一共交了18次
第6个点死活过不去
妄想@管理员放宽时限,然后被暴政拒绝了

如图




据悉,该管理员还来到501进行了实地考察,并对当事人代码的复杂度进行了质疑

“那你就卡常去吧”

他如是说

于是我就又乖乖卡了两小时的常总算是过了