可持久化线段树 & Trie树

  1. 1 【bzoj 3673】可持久化并查集 by zky
  2. 2 【bzoj 3674】可持久化并查集加强版
  3. 3 【bzoj 3261】最大异或和

话说主席树和可持久化线段树到底是一个东西吗?
这里的可持久化线段树是指查询历史情况的线段树

1 【bzoj 3673】可持久化并查集 by zky

n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0
0<n,m<=2×10^4

把可持久化线段树的叶子节点当做一个数组
所以就有了可持久化数组,2333
要按秩合并(启发式合并)(话说随便合并也可以过的)
初始所有集合秩为0
合并把秩小的树根的父亲设为秩大的树根
如果秩相同,则随便选取一个作为父节点并将它的秩+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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=400000;
int n,m,sz,root[20005],fa[N],deep[N],ls[N],rs[N];
void Build(int l,int r,int &x)
{
x=++sz;
if(l==r) {fa[x]=l;return;}
int mid=(l+r)>>1;
Build(l,mid,ls[x]);Build(mid+1,r,rs[x]);
}
int Quary(int l,int r,int rt,int x,int v)
{
if(l==r) return fa[x]==l?x:Quary(1,n,rt,rt,fa[x]);
int mid=(l+r)>>1;
if(v<=mid) return Quary(l,mid,rt,ls[x],v);
else return Quary(mid+1,r,rt,rs[x],v);
}
void Insert(int l,int r,int x,int &y,int f1,int f2)
{
y=++sz;
ls[y]=ls[x];rs[y]=rs[x];
fa[y]=fa[x];deep[y]=deep[x];
if(l==r) {fa[y]=f1;return;}
int mid=(l+r)>>1;
if(f2<=mid) Insert(l,mid,ls[x],ls[y],f1,f2);
else Insert(mid+1,r,rs[x],rs[y],f1,f2);
}
void Add(int l,int r,int x,int v)
{
if(l==r) {deep[x]++;return;}
int mid=(l+r)>>1;
if(v<=mid) Add(l,mid,ls[x],v);
else Add(mid+1,r,rs[x],v);
}
int main()
{
scanf("%d%d",&n,&m);
Build(1,n,root[0]);
for(int i=1,f1,f2,k,a,b;i<=m;i++)
{
scanf("%d%d",&k,&a);
if(k==1)
{
scanf("%d",&b);
root[i]=root[i-1];
f1=Quary(1,n,root[i],root[i],a);f2=Quary(1,n,root[i],root[i],b);
if(f1==f2) continue;
if(deep[f1]<deep[f2]) swap(f1,f2);
Insert(1,n,root[i-1],root[i],fa[f1],fa[f2]);
if(deep[f1]==deep[f2]) Add(1,n,root[i],fa[f1]);
}
else if(k==2) root[i]=root[a];
else
{
scanf("%d",&b);
root[i]=root[i-1];
printf("%d\n",(Quary(1,n,root[i],root[i],a)==Quary(1,n,root[i],root[i],b)));
}
}
}

2 【bzoj 3674】可持久化并查集加强版

n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0
请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0
0<n,m<=2×10^5

其实只是强制在线+范围加大嘛

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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=5000000;
int n,m,sz,lastans,root[200005],fa[N],deep[N],ls[N],rs[N];
void Build(int l,int r,int &x)
{
x=++sz;
if(l==r) {fa[x]=l;return;}
int mid=(l+r)>>1;
Build(l,mid,ls[x]);Build(mid+1,r,rs[x]);
}
int Quary(int l,int r,int rt,int x,int v)
{
if(l==r) return fa[x]==l?x:Quary(1,n,rt,rt,fa[x]);
int mid=(l+r)>>1;
if(v<=mid) return Quary(l,mid,rt,ls[x],v);
else return Quary(mid+1,r,rt,rs[x],v);
}
void Insert(int l,int r,int x,int &y,int f1,int f2)
{
y=++sz;
ls[y]=ls[x];rs[y]=rs[x];
fa[y]=fa[x];deep[y]=deep[x];
if(l==r) {fa[y]=f1;return;}
int mid=(l+r)>>1;
if(f2<=mid) Insert(l,mid,ls[x],ls[y],f1,f2);
else Insert(mid+1,r,rs[x],rs[y],f1,f2);
}
void Add(int l,int r,int x,int v)
{
if(l==r) {deep[x]++;return;}
int mid=(l+r)>>1;
if(v<=mid) Add(l,mid,ls[x],v);
else Add(mid+1,r,rs[x],v);
}
int main()
{
scanf("%d%d",&n,&m);
Build(1,n,root[0]);
for(int i=1,f1,f2,k,a,b;i<=m;i++)
{
scanf("%d%d",&k,&a); a^=lastans;
if(k==1)
{
scanf("%d",&b); b^=lastans;
root[i]=root[i-1];
f1=Quary(1,n,root[i],root[i],a);f2=Quary(1,n,root[i],root[i],b);
if(f1==f2) continue;
if(deep[f1]<deep[f2]) swap(f1,f2);
Insert(1,n,root[i-1],root[i],fa[f1],fa[f2]);
if(deep[f1]==deep[f2]) Add(1,n,root[i],fa[f1]);
}
else if(k==2) root[i]=root[a];
else
{
scanf("%d",&b); b^=lastans;
root[i]=root[i-1];
lastans=Quary(1,n,root[i],root[i],a)==Quary(1,n,root[i],root[i],b);
printf("%d\n",lastans);
}
}
}

3 【bzoj 3261】最大异或和

给定一个非负整数序列{a},初始长度为N。
有M个操作,有以下两种操作类型:
1 、A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N+1。
2 、Q l r x:询问操作,你需要找到一个位置 p,满足 l<=p<=r,使得:
a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。

可持久化trie树
b[i]表示a[1] xor a[2] ... xor a[i]
求max(b[p-1]^b[n]^x) (l<=p<=r)
据说前面加一个0会好处理
因为不然每次要查询trie[l-2]和trie[r-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
#include<cstdio>
#define N 600005
using namespace std;
int n,m,sz,a[N],root[N],c[N*24][2],sum[N*24];
char s[1];
void Insert(int x,int &y,int v,int k)
{
if(!y) y=++sz;
sum[y]=sum[x]+1;
if(k==-1) return;
int t=(v>>k)&1;
c[y][!t]=c[x][!t];
Insert(c[x][t],c[y][t],v,k-1);
}
int Quary(int x,int y,int v)
{
int z=0;
for(int i=24,t;i>=0;i--)
{
t=(v>>i)&1;
if(sum[c[y][t^1]]-sum[c[x][t^1]])
z+=1<<i,x=c[x][t^1],y=c[y][t^1];
else x=c[x][t],y=c[y][t];
}
return z;
}
int main()
{
scanf("%d%d",&n,&m);n++;
for(int i=2,x;i<=n;i++)
scanf("%d",&x),a[i]=a[i-1]^x;
for(int i=1;i<=n;i++)
Insert(root[i-1],root[i],a[i],24);
for(int i=1,x,y,z;i<=m;i++)
{
scanf("%s%d",s,&x);
if(s[0]=='A')
{
a[++n]=a[n-1]^x;
Insert(root[n-1],root[n],a[n],24);
}
else
{
scanf("%d%d",&y,&z);
printf("%d\n",Quary(root[x-1],root[y],a[n]^z));
}
}
}