利用可持久化01Trie解决区间异或一类问题
为了补校赛网络的I题，就去看了异或粽子，然后就看到了Trie以及可持久化01Trie，进而就有了这篇博客qaq
借助这几道题学习一番可持久化01Trie的有关知识
P4735 最大异或和
题目要求区间中某个位置p∈[L, R]使得a[p] ^ a[p + 1]^ ... ^ a[n] ^ x最大，其中p, L, R给定，允许在该序列末尾动态添加数字。首先根据异或的性质等价转化要求的表达式：``a[p] ^ a[p + 1]^ … ^ a[n] ^ x = x ^ sum ^ a[1] ^ a[2] ^ … ^ a[p - 1] `，其中sum是整个序列的异或值；因而在某个给定的状态下，我们只需要找位置p-1使得其前缀异或值和x^sum异或值最大即可。为了完成动态修改、查询的工作，我们使用可持久化01Trie，其思想与主席树类似（尽管我还没学但是不妨碍我学会01Trie)。
可持久化01Trie的核心思想在于：在插入一个新数的时候用该数本身拥有的值新建节点，对于本身不拥有的值则继承上一颗树的情况，即L11、L12所示。
而在本题中因为要查找一段区间最优的一个异或值，所以为了方便查找额外设置size数组记录当前节点拥有字符串的个数。如果同一个节点在两个不同版本之间的size值不同，那么说明这段版本之间一定拥有一个含有这个值的串，所以应该将指针沿着这个方向前进。因为本题要求异或值最大，所以我们找方向边是否存在，存在的话毫无疑问应该从反向边往后查找，这也就是query函数所完成的工作。
此外，因为我们分析出来如果给定区间[L, R]，那么最终我们要找的前缀和应该在[L - 1, R - 1]之中，用Trie的版本号表示就意味找R-1和L - 2的差值。为了防止溢出等麻烦的问题，我们添加冗余项0，这样原序列整体下标后移1位，所以就变成了查找R与L - 1的差值。
最后，因为初始给定3e5的原始序列和操作，所以最终串的长度有可能成为6e5！又因为可持久化Trie存了每个版本的信息，所以每多一个版本，就会再花费N个节点，N是表达一个数最多需要的位数，故总复杂度应该设置为6e5 * N。不然RE
1const int N = 24;
2const itn maxn = 6e5 * N + 10;
3
4struct TRIE{
5 int version = 0, top = 0;
6 int ch[maxn][2], root[maxn];;
7 int size[maxn];
8
9 void insert(int x){
10 int rot = root[version];
11 root[++version] = ++top;
12 for(int i = N - 1; i >= 0; i--){
13 int id = (x >> i) & 1;
14 ch[top][id] = top + 1; //新建
15 ch[top][!id] = ch[rot][!id]; //继承
16 size[top] = size[rot] + 1;
17 top++; rot = ch[rot][id];
18 }
19 size[top] = size[rot] + 1;
20 }
21
22 int query(int L, int R, itn x){
23 int l = root[L], r = root[R];
24 int ans = 0;
25 for(int i = N - 1; i >= 0; i--){
26 int id = (x >> i) & 1;
27 if(size[ch[r][!id]] - size[ch[l][!id]] > 0){
28 ans |= 1 << i;
29 r = ch[r][!id]; l = ch[l][!id];
30 }
31 else{
32 r = ch[r][id];
33 l = ch[l][id];
34 }
35 }
36 return ans;
37 }
38};
39
40TRIE tree;
41
42int main(){
43// Fastin;
44 int n, m; scanf("%d %d", &n, &m);
45 int sum = 0;
46
47 tree.insert(0);
48 for(int i = 0; i < n; i++) {
49 int x; scanf("%d", &x); sum ^= x;
50 tree.insert(sum);
51 }
52 int l, r, x;
53 for(int i = 0; i < m; i++){
54 char op[2];
55 scanf("%s", op);
56 if(op[0] == 'A'){
57 scanf("%d", &x); sum ^= x;
58 tree.insert(sum);
59 }
60 else{
61 scanf("%d %d %d", &l, &r, &x);
62 printf("%d\n", tree.query(l - 1, r, x ^ sum));
63 }
64 }
65 return 0;
66}P5283 [十二省联考2019]异或粽子
前置知识点：P1631 序列合并
简而言之，用堆$O(logn)$维护n个有序队列各自的最大值，将$n ^2$的比较变成了$n$的比较，值得学习的手法！
1int a[maxn], b[maxn];
2struct NODE{
3 int i, j, sum;
4 bool operator <(const NODE &b)const{
5 return sum > b.sum;
6 }
7};
8priority_queue<NODE> pq;
9
10int main(){
11// Fastin;
12 int n; scanf("%d", &n);
13 for(int i = 0; i < n; i++) scanf("%d", a + i);
14 for(int i = 0; i < n; i++) scanf("%d", b + i);
15 for(int i = 0; i < n; i++) pq.push({i, 0, a[i] + b[0]});
16
17 int times = n;
18 while(times--){
19 NODE temp = pq.top(); pq.pop();
20 printf("%d", temp.sum); if(times) printf(" "); else printf("\n");
21
22 int i = temp.i, j = temp.j + 1;
23 if(j >= n) continue;
24 pq.push({i, j, a[i] + b[j]});
25 }
26 return 0;
27}异或粽子
给出$n <= 5e5$的序列，问所有区间异或值中前$k <= 2e5$大之和。
首先做异或前缀，这样就可以用两点表示一段区间，接下里将这些前缀插入到可持久化01Trie中。下面考虑如何查找前k大的每一个数，主要思想与P1631序列合并类似：我们枚举右端点j，对每一个右端点所拥有的一串有序序列从大到小一个个插入到堆中。那么如何维护这个有序队列呢？我们设置结构[i, j, l, r, sum]表示右端点在j，在区间[l, r]中找到的最优左端点是i，其异或值是sum。那么当我们从堆中拿出一个节点后，下一个就应该从右端点在j，左端点处于区间[l, i - 1]和区间[i + 1, r]中找更大的结果并放入堆中。我自己写的时候没有判断哪一边更大而是两边都放进去了 因为不想判断左极限右极限的情况 仅仅多一个log2的复杂度问题不大
不过这里面有一些地方很绕…我想了很久才基本理清楚。qaq
如果初始序列从1开始编号，那么如果当前右端点确定为i，左端点可选区间就在[1, i]，在前缀的表达中就是异或上[0, i - 1]，所以在Trie中的查找就是版本i - 1减去版本0 - 1之间的情况。这样会出现-1这种不太妙的东西，所以我们添加冗余项0，那么就只需要在版本i和版本0之间求差值。
最后有一个关于可持久化Trie相关的数据范围的问题。。坑
因为要存版本，所以会多开maxn个节点！
然而这不意味着要把N开大，因为N开大插入的每一个数占用的节点也会对应变大！
所以应该在maxn中添加一些冗余的位置，不修改N的最大值！
1const int N = 33;
2const itn maxn = 5e5 * (N + 5) + 10;
3
4struct TRIE{
5 int version = 0, top = 0;
6 int ch[maxn][2], root[maxn];;
7 int size[maxn], id[maxn];
8
9 void insert(ll x, int id){
10 int rot = root[version];
11 root[++version] = ++top;
12 for(int i = N - 1; i >= 0; i--){
13 int id = (x >> i) & 1;
14 ch[top][id] = top + 1;
15 ch[top][!id] = ch[rot][!id];
16 size[top] = size[rot] + 1;
17 top++; rot = ch[rot][id];
18 }
19 size[top] = size[rot] + 1;
20 this->id[top] = id;
21 }
22
23 void query(int L, int R, ll x, int &k, ll &sum){
24 int l = root[L], r = root[R];
25 sum = 0;
26 for(int i = N - 1; i >= 0; i--){
27 int id = (x >> i) & 1;
28 if(size[ch[r][!id]] - size[ch[l][!id]] > 0){
29 sum |= 1ll << i;
30 r = ch[r][!id]; l = ch[l][!id];
31 }
32 else{
33 l = ch[l][id];
34 r = ch[r][id];
35 }
36 }
37 k = this->id[r];
38 }
39};
40TRIE tree;
41
42//右端点j给定，每次找i；当前区间为[l, r]
43struct NODE{
44 int i, j, l, r;
45 ll sum;
46 NODE(int _i, int _j, int _l ,itn _r, ll _sum){
47 i = _i; j = _j; l = _l; r = _r; sum = _sum;
48 }
49 bool operator <(const NODE &b)const{
50 return sum < b.sum;
51 }
52};
53
54ll a[500010];
55priority_queue<NODE> pq;
56
57int main(){
58// Fastin;
59 tree.insert(0, 0);
60
61 int n, m; scanf("%d %d", &n, &m);
62 for(int i = 1; i <= n; i++){
63 scanf("%lld", a + i);
64 a[i] ^= a[i - 1];
65 tree.insert(a[i], i);
66 }
67
68 int k; ll sum;
69 for(int i = 1; i <= n; i++){
70 //查询[1, i]
71 tree.query(0, i, a[i], k, sum);
72 //[k + 1, i]
73 pq.push(NODE(k + 1, i, 1, i, sum));
74 }
75
76 ll ans = 0;
77 while(m--){
78 NODE temp = pq.top(); pq.pop();
79 ans += temp.sum;
80 int i = temp.i, j = temp.j, l = temp.l, r = temp.r;
81
82 if(i - 1 >= l){
83 //划分左端点，查询[l, i - 1]中最合适的端点。
84 tree.query(l - 1, i - 1, a[j], k, sum);
85 pq.push(NODE(k + 1, j, l, i - 1, sum));
86 }
87 if(i + 1 <= r){
88 tree.query(i, r, a[j], k, sum);
89 pq.push(NODE(k + 1, j, i + 1, r, sum));
90 }
91 }
92 printf("%lld\n", ans);
93 return 0;
94}2020校赛网络赛I 第k大区间
xdoj好像最近升级升爆了交不了题
不知道自己正确与否就又顺手用写了个对拍程序。。原来MacOS也支持system函数那就好写了！
之前尝试过用管道实现进程通信….然而失败了….qaq
在1000的范围内对拍下来没有不一样的结果，那么姑且认为是AC了，等之后OJ修好了再康康。
这道题与异或粽子不同的地方在于不需要查询前k的每一项，而只需要知道第k大确切是多少，从而k的范围也变大到了$n^2$的数量级。那么就回到了梦最开始的地方，二分答案，通过持久01Trie检查是否有足够多的大于等于该值的区间。
同样是区间查询，所以先做前缀异或和，将区间查询转换为点对查询。然后枚举右端点$j$，看其对应的左端点有哪些满足异或上$a[j]$后比二分的答案更大。因而我们在Trie中维护size表示节点拥有的子串个数，查询时按照如下法则：
- 如果二分答案在该位为0，那么$a[j]$在该位的值与其反向边所拥有的所有串异或全部都可以取，同向边则需要进一步dfs看更低位的情况。
- 如果二分答案在该位为0，那么必须走反向边才能满足这一位不比1小，素以从反向边开始进一步dfs；这里要判断一下是否存在至少一个反向边，如果没有直接返回0即可。（因为终点根据wei是否小于0判断，小于0返回1，其前提是前面的每一位都相等，所以不允许之前有不存在的情况）
1const int N = 32;
2const itn maxn = 1e5 * (N + 5) + 10;
3
4struct TRIE{
5 int version = 0, top = 0;
6 int ch[maxn][2], root[maxn];;
7 int size[maxn];
8
9 void insert(ll x){
10 int rot = root[version];
11 root[++version] = ++top;
12 for(int i = N - 1; i >= 0; i--){
13 int id = (x >> i) & 1;
14 ch[top][id] = top + 1;
15 ch[top][!id] = ch[rot][!id];
16 size[top] = size[rot] + 1;
17 top++; rot = ch[rot][id];
18 }
19 size[top] = size[rot] + 1;
20 }
21
22 //查询[L + 1, R]区间中异或上x后大于等于key的数量
23 ll query(int l, int r, ll x, ll key, int wei){
24 //什么时候会进行递归？前面的所有位都相等的情况！
25 if(wei < 0) return 1;
26 ll res = 0;
27
28 int op = (key >> wei) & 1, id = (x >> wei) & 1;
29 if(op == 0){
30 //key的这一位是0，结果可以是0/1
31 res += size[ch[r][!id]] - size[ch[l][!id]];
32 if(size[ch[r][id]] - size[ch[l][id]] > 0)
33 res += query(ch[l][id], ch[r][id], x, key, wei - 1);
34 }
35 else if(size[ch[r][!id]] - size[ch[l][!id]] > 0)
36 res += query(ch[l][!id], ch[r][!id], x, key, wei - 1);
37 return res;
38 }
39};
40TRIE tree;
41
42int n, m;
43ll a[100010];
44
45bool check(ll x){
46 /*对于每个右端点j，查询左端点[1, j]看多少个区间的值大于等于x
47 前缀左端点区间[0, j - 1] 查询[-1, j - 1] 添加冗余项0 故查询[0, j]
48 */
49 ll ans = 0;
50 for(int i = 1; i <= n; i++){
51 int l = tree.root[0], r = tree.root[i];
52 ans += tree.query(l, r, a[i], x, N - 1);
53 }
54
55 return ans >= m;
56}
57
58int main(){
59// Fastin;
60 tree.insert(0);
61 scanf("%d %d", &n, &m);
62 for(int i = 1; i <= n; i++){
63 scanf("%lld", a + i);
64 a[i] ^= a[i - 1];
65 tree.insert(a[i]);
66 }
67 ll left = 0, right = (1ll << 32) - 1, middle;
68 while(left < right){
69 middle = (left + right + 1) >> 1;
70 if(check(middle)) left = middle;
71 else right = middle - 1;
72 }
73 printf("%lld\n", left);
74 return 0;
75}