可持久化线段树 & Trie树

OI&ACM, 可持久化数据结构
  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));
		}
	}
}
可持久化线段树 可持久化trie树