【平衡树】平衡树练习

平衡树

传送阵：CodeVS4244

平衡树模板

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 600000
int n,m,x,root,tot,fa[N],size[N],data[N],son[N][2],val[N];
int getint(){
	int sum=0; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
void rotate(int x,int w){
	int y=fa[x];
	size[y]=size[y]-size[x]+size[son[x][w]];
	size[x]=size[x]+size[y]-size[son[x][w]];
	son[y][w^1]=son[x][w]; if (son[x][w]) fa[son[x][w]]=y;
	fa[x]=fa[y]; if (fa[y]){if (son[fa[y]][0]==y) son[fa[y]][0]=x; else son[fa[y]][1]=x;}
	fa[y]=x; son[x][w]=y;
}
void splay(int x){
	while (fa[x]){
		int y=fa[x];
		if (fa[y]==0){if (x==son[y][0]) rotate(x,1); else rotate(x,0);}
		else{
			if (x==son[y][0]){
				if (y==son[fa[y]][0]){rotate(y,1); rotate(x,1);}//zig-zig
				else{rotate(x,1); rotate(x,0);}//zig-zag
			}
			else{
				if (y==son[fa[y]][0]){rotate(x,0); rotate(x,1);}//zag-zig
				else{rotate(y,0); rotate(x,0);}//zag-zag
			}
		}
	}
	root=x;
}
int search(int x,int k){
	while (data[x]!=k){
		if (k<data[x]){if (son[x][0]==0) return x; x=son[x][0];}
		else{if (son[x][1]==0) return x; x=son[x][1];}
	}
	return x;
}
	
void ins(int x){
	if (!tot){data[++tot]=x; fa[tot]=0; size[tot]=1; root=1; val[1]=1; return;}
	int k=search(root,x),kk; bool flag;
	if (data[k]==x){val[k]++; kk=k; flag=1;}
	else{
		data[++tot]=x; fa[tot]=k; size[tot]=1; val[tot]=1; flag=0;
		if (x<data[k]) son[k][0]=tot; else son[k][1]=tot;
	}
	while (k){size[k]++; k=fa[k];}
	if (flag) splay(kk); else splay(tot);
}
int main(){
	n=getint(); m=getint();
	for (int i=1;i<=n;i++){x=getint(); ins(x);}
	for (int i=1;i<=m;i++){x=getint(); printf("%d ",data[search(root,x)]==x);}
	
	return 0;
}