LuoguP4735最大异或和（可持久化Trie）

Posted on |

Problem

题目传送门

给一个序列${ a}$，长度为n.

有m个操作.

1.在序列末尾添加一个x.

2.找到一个$p∈[l,r]$，使得$a[p]⊕a[p+1]⊕…⊕a[N]⊕x$最大，其中N为序列的长度。

Solution

记$all$为$a[1]⊕a[2]⊕a[3]…⊕a[N]$

询问即为找到一个$p∈[l,r]$ 使得$a[1]⊕a[2]⊕a[3]…⊕a[p]⊕all⊕x$最大。

所以，我们只需要维护序列${a}$的前缀异或和即可。

这里引出了一个算法：

可持久化Trie

听起来十分高大上。

其实就是用一颗01Trie维护每一位的出现次数。

和可持久化主席树的实现差不多。

网上的板子都过于优秀（神仙）

受到右边大佬启发后,开始研究如何像写主席树一样写可持久化Trie.

个人感觉很好理解。

Code

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
78
79
#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
int INF = (1 << 25) - 1;
const int Maxn = 3e5 + 10, Log = 25;
struct SGT{
	int ls, rs, sum;
}tre[Maxn << 6];
int cnt, p[Maxn << 1], Pow[30], root[Maxn << 1];
void build(int &rt, int grt,int pos, int T){
	tre[rt = ++cnt] = tre[grt];
	tre[rt].sum++;
	if(T < 0) return;
	if(!(pos & Pow[T])) build(tre[rt].ls, tre[grt].ls, pos, T - 1);
	else build(tre[rt].rs, tre[grt].rs, pos, T - 1);
}
int Query(int a, int b, int pos, int T){
	if(T < 0) return 0;
	bool l = (tre[tre[b].ls].sum - tre[tre[a].ls].sum > 0);
	bool r = (tre[tre[b].rs].sum - tre[tre[a].rs].sum > 0);
	bool now = (pos & Pow[T]) > 0;
	if(!r) return (now) * Pow[T] + Query(tre[a].ls, tre[b].ls, pos, T - 1);
	if(!l) return (!now) * Pow[T] + Query(tre[a].rs, tre[b].rs, pos, T - 1);
    //一边没有数，显然只能往另一边走。
	if(now) return Pow[T] + Query(tre[a].ls, tre[b].ls, pos, T - 1);
	return Pow[T] + Query(tre[a].rs, tre[b].rs, pos, T - 1);
    //贪心过程，因为位数高具有绝对优势。

}
void init(int n){
	p[0] = 0, Pow[0] = 1;
	build(root[0], 0, 0, Log);
	for (int i = 1; i <= Log; ++i) Pow[i] = Pow[i - 1] << 1;
	for (int i = 1; i <= n; ++i){
		p[i] = read() ^ p[i - 1];
		build(root[i], root[i - 1], p[i - 1], Log);
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int n = read(), m = read();
	init(n);
	int num = n;
	while(m--){
		char opt = getchar();
		while(opt != 'A' && opt != 'Q') opt = getchar();
		if(opt == 'A') {
			++num,p[num] = p[num - 1] ^ read();
			build(root[num],root[num - 1], p[num - 1], Log);
		}
		else {
			int l = read(), r = read(), x = read();
			printf("%d\n",Query(root[l - 1], root[r], x ^ p[num], Log));
		}
	}
	return 0;
}