没学过持久化的表示老是想错了,搞了好几天才弄懂。此题是可持续化trie
可持久化的前提:在修改的过程中,数据结构本身的拓扑结构不会发生改变。
可持久化的数据结构例子:trie树,线段树——主席树,堆,树状数组
不可持久化的数据结构例子:平衡树(左旋右旋后,拓扑结构会发生改变)
可持久化数据结构解决的问题:我们希望把每次修改的版本都记录下来(类似git工具)
可以存下来数据结构的所有历史版本
核心思想:只会记录每一个版本与前一个版本不一样的结点
a[p] ^ a[p+1] ^ ... ^ a[N] ^ x = s[p-1] ^ s[N] ^ x
摘自:彩神
思路
- 上面各个颜色代表各个版本
持久化总结:通俗的语言:假如当要插入个字符串abc
时, 检查上个版本root
是否存在 除了从a
出发的路径, 有则将当前root
连接过去, 即继承旧版本。然后再加入新点a
。 当走到b
时, 检查是否存在 除了从b
出发的路径,即是否有ac…, ad…, ae,…,..类似的字符串,有则要(连接)过去,然后再加入b
。
此题有三个点
- 因为求的是区间异或, 则可以使用前缀异或和的数组插入
trie
树中。 - 只有对
R
的范围限制(即$1\leq x \leq R$): 只需找到root[R]
,即第R
个版本即可, 这是对可持久化的应用。 - 对于
L
的范围限制,只需要每个节点保存能被更新的最大的下标即可,因为假如有某个点(在范围内)要经过该节点,则这个节点被更新到它的id
, 则可以走这条路径。
代码(细节有点多..)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 600010, M = N * 25; //10^7最多24位
int n, m;
//前缀异或和
int s[N];
//01trie树、每个节点的访问最大下标
int tr[M][2], max_id[M];
//不同的版本的root编号
int root[N], idx;
//当前插入s[i], i是下标, 二进制第k位, p上个版本, q当前版本
void insert(int i, int k, int p, int q){
if(k < 0){
max_id[q] = i;
return;
}
int v = s[i] >> k & 1;
//p中是否有q 新插入节点的路径
if(p) tr[q][v ^ 1] = tr[p][v ^ 1];
tr[q][v] = ++ idx;
////往下走
//(没有idx为0的,所有p如果不满足也可以往下,一直不满足)
insert(i, k - 1, tr[p][v], tr[q][v]);
max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}
//右边界, 常数a[n]^x, 左边界
int query(int root, int C, int L){
int p = root;
for(int i = 23; i >= 0; i --){
int v = C >> i & 1;
if(max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
else p = tr[p][v];
}
return C ^ s[max_id[p]];
}
int main(){
scanf("%d%d", &n, &m);
//给max的赋最小
max_id[0] = -1;
root[0] = ++ idx;
insert(0, 23, 0, root[0]);
for(int i = 1; i <= n; i ++){
int x;
scanf("%d", &x);
s[i] = s[i - 1] ^ x;
root[i] = ++ idx;
insert(i, 23, root[i - 1], root[i]);
}
char op[2];
int l, r, x;
while(m --){
scanf("%s", op);
if(*op == 'A'){
scanf("%d", &x);
n ++;
s[n] = s[n - 1] ^ x;
root[n] = ++ idx;
insert(n, 23, root[n - 1], root[n]);
}
else{
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
}
}
return 0;
}
max_id[0] = -1不这样赋值的话什么情况下会出现问题?
请问一下“检查上个版本root是否存在 除了从a 出发的路径, 有则将当前root连接过去”这个在哪里有体现
在这个题目中没有体现,好像这个题目只有0和1两条路
(太久了,有点记不清)如果是看我上面的图,要连接旧版本则需要将a~z遍历一遍, 这题不需遍历,只要两条路。
请问一下那是复制节点的时候v^1是什么意思
将旧版本连上