平衡树（treap或splay？）

推荐想学的同学别看我的博客 学！别人写的会清楚很多，我是没有讲解的。很烂的

呃几乎是最后一个专题了罢，不知不觉间便也是三年，三年，大抵也后悔过，放弃过，麻木过，颓唐过，失望过。不过反正总还能跌跌撞撞的走下去。也许，这次noip，我不知道做了多少准备。也许很多也许很少，也许拼尽全力也许不值一提。这一切都不重要了。反正结束亦是开始，命运的齿轮倒也还能在一切消逝前转着。得承认的，我不是什么好东西，也没有多聪明，懒，爱抱怨，老想着结束。可最终这样再看看，路上的风风雨雨，平平淡淡，每一个无法预期的清晨与夜晚，却也让人怀着期待，怀着清爽。无论是来的路上，又或是离的路上，无可替代的，是那些走来又走过的人们，是不是想过后悔呢？大概是有的，但是！绕远的路，总有风景。哈哈哈时间不多了，别怕，我们会走到最后。
咳咳咳！来看看这个平衡树，我们将用一天半的时间将其搞定。P3369 【模板】普通平衡树，那么其实这东西操作不多，我其实也不是很想学这个，感觉没有treap好用的说。splay

#include
using namespace std;
int n,m;
struct node 
{
	int lc,rc,val,cnt,tk,sz;
};
node tr[1100010];
int tot=0,root;
int bn(int val)
{
	tot++;
	tr[tot].val=val;
	tr[tot].tk=rand()%10000011;
	tr[tot].cnt=tr[tot].sz=1;
	tr[tot].lc=tr[tot].rc=0;
	return tot;
}

void up(int p)
{
	tr[p].sz=tr[tr[p].lc].sz+tr[tr[p].rc].sz+tr[p].cnt;
	return ;
}
int yx(int p)
{
	int q=tr[p].lc;
	tr[p].lc=tr[p].rc;
	tr[q].rc=p;
	tr[q].sz=tr[p].sz;
	up(p);
	return q;
}
int zx(int p)
{
	int q=tr[p].rc;
	tr[p].rc=tr[p].lc;
	tr[q].lc=p;
	tr[q].sz=tr[p].sz;
	up(p);
	return q;
}
void add(int &p,int val)
{
	if(!p) 
	{
		p=bn(val);
		return ;
	} 
	tr[p].sz++;
	if(val==tr[p].val) 
	{
		tr[p].cnt++;
		return ;
	}
	if(val<tr[p].val)
	{
		add(tr[p].lc,val);
		if(tr[p].tk<tr[tr[p].lc].tk) yx(p);
	}
	else 
	{
		add(tr[p].rc,val);
		if(tr[p].tk<tr[tr[p].rc].tk) zx(p);
	}
	return ;
}
void dl(int &p,int val)
{
	if(!p) return ;
	tr[p].sz--;
	if(val==tr[p].val) 
	{
		if(tr[p].cnt>1) 
		{
			tr[p].cnt--;
			return ;
		}
		if(!tr[p].lc||!tr[p].rc) p=tr[p].lc+tr[p].rc;
		else if(tr[tr[p].lc].tk>tr[tr[p].rc].tk)
		{
			yx(p);
			dl(tr[p].rc,val);
		}
		else
		{
			zx(p);
			dl(tr[p].lc,val);
		}
		return ;
	}
	if(val<tr[p].val) dl(tr[p].lc,val);
	else dl(tr[p].rc,val);
	return ; 
}
int findmax(int val)
{
	int p=root,ans=0;
	while(p)
	{
		if(tr[p].val<val)
		{
			ans=tr[p].val;
			p=tr[p].rc;
		}
		else p=tr[p].lc;
	}
	return ans;
}
int findmin(int val)
{
	int p=root,ans=0;
	while(p)
	{
		if(tr[p].val>val)
		{
			ans=tr[p].val;
			p=tr[p].lc;
		}
		else p=tr[p].rc;
	}
	return ans;	
}
int findnum(int p,int val)
{
//	printf("*");
	if(!p) return 0;
	if(tr[p].val==val) return tr[tr[p].lc].sz+1;
	else if(val<tr[p].val) return findnum(tr[p].lc,val);
	else return findnum(tr[p].rc,val)+tr[tr[p].lc].sz+tr[p].cnt;
}
int findval(int p,int k)
{
	if(!p) return 0;
	if(tr[tr[p].lc].sz>=k) return findval(tr[p].lc,k);
	if(tr[tr[p].lc].sz+tr[p].cnt>=k) return tr[p].val;
	return findval(tr[p].rc,k-tr[tr[p].lc].sz-tr[p].cnt);
}
int main()
{
//	freopen("phs.out","w",stdout);
	for (int i=1;i<=1000;i++) tr[i].lc=tr[i].rc=tr[i].val=tr[i].cnt=tr[i].tk=tr[i].sz=0;
	root=0;
	scanf("%d",&n);
	while(n--)
	{
		int pd;
		scanf("%d",&pd);
		if(pd==1) 
		{
			int val;
			scanf("%d",&val);
			add(root,val);
		}
		else if(pd==2)
		{
			int val;
			scanf("%d",&val);
			dl(root,val);
		}
		else if(pd==3)
		{
			int val;
			scanf("%d",&val);
			printf("%d\n",findnum(root,val));
		}
		else if(pd==4)
		{
			int val;
			scanf("%d",&val);
			printf("%d\n",findval(root,val));
		}
		else if(pd==5)
		{
			int x;
			scanf("%d",&x);
			printf("%d\n",findmax(x));
		}
		else 
		{
			int x;
			scanf("%d",&x);
			printf("%d\n",findmin(x));
		}
	}
	return 0;
}
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

我打一遍再说吧。（=，=）其实还是想学treap的splay的左右旋转操作好难啊。草我还是学一下，treap吧，害。麻烦呜呜呜呜。下定决心了，刚刚浪费了半天考虑学什么呜呜呜我是智障。想ta。
嗯treap的话我推荐是无旋的那种，明天早上写。 注意一下这个打法中merge是的先后顺序是十分重要的，因为有大小之分。导致于我调了半天呜呜呜其他重要的东西放代码里。推荐：https://www.bilibili.com/video/BV1ft411E7JW?。p=1&vd_source=f51708a79de2172437e75278f8c832e0的视频。学习

#include
using namespace std;
int n,m,len=0,root;
struct treap
{
	int l,r,val,key,cnt,siz;
};treap tr[100001];
int btnew(int val)//新开一个节点 
{
	tr[++len].val=val;tr[len].key=rand();
	tr[len].siz=1;
	return len;
}
void update(int now)
{
	tr[now].siz=tr[tr[now].l].siz+tr[tr[now].r].siz+1;
	return ; 
 } 
void split(int now,int val,int &x,int &y)//根据子树的点值来分裂，一半是<=的，另一半是大于的 
{
	if(!now) x=y=0;//如果我这个节点不存在 
	else 
	{
		if(tr[now].val<=val) x=now,split(tr[now].r,val,tr[now].r,y);
		//若我这个节点的值小于等于val，那么我左子树肯定也，不过右子树还要再看看 
		//所以将右子树大小传进去 
		else y=now,split(tr[now].l,val,x,tr[now].l); 
		//同上，问题在于它会更更新部分节点的左右儿子，使得整棵树完全分裂 
		update(now);
	}
	return ;
}
int merge(int x,int y) //合并两棵树，保证了x里面所有的元素
{
	if(!x||!y) return x+y;//如果其中有一个不存在 
	//维护二叉堆的性质 
	if(tr[x].key>tr[y].key)//这样理解：key维护上下，val维护左右 
	{
		//那么这个就是右下，但可能原来有了，所以要合并 
		tr[x].r=merge(tr[x].r,y); 
		update(x);return x;	
	}	
	else
	{
		//合并到左下 
		tr[y].l=merge(x,tr[y].l);
		update(y);return y;	
	} 
} 
void ins(int val)
{
	int x,y;split(root,val,x,y);//先将val拆走，那么直接插入即可 
	root=merge(merge(x,btnew(val)),y);//注意了要分先后顺序啊 
	return ; 
}

void dl(int val)//删除 
{
	int x,y,z;split(root,val,x,z);split(x,val-1,x,y);//分离val-1与val
	//剩下的就是值为val的，发现可能不止一个。那么我们再合并其子树就行 
	y=merge(tr[y].l,tr[y].r); 
	root=merge(merge(x,y),z);
	return ;
}
int getrank(int val)
{
	int x,y,rt;split(root,val-1,x,y);//查排名当然简单 
	rt=tr[x].siz+1;root=merge(x,y);
	return rt;
}
int getval(int rank)//根据排名找值 
{
	int now=root;
	while(now)
	{
		if(tr[tr[now].l].siz+1==rank) break;//根直接就是 
		else if(tr[tr[now].l].siz>=rank) now=tr[now].l;//往左走的时候 
		else rank-=(tr[tr[now].l].siz+1),now=tr[now].r;//往右走的时候要减去左边的子树 
	}	
	return tr[now].val;
}
int getper(int val)//1到val-1中最大的数（将val-1）分离出去 
{
	int x,y;split(root,val-1,x,y);
	int now=x;while(tr[now].r) now=tr[now].r;//找最大 
	int rt=tr[now].val;root=merge(x,y);//合并啊啊啊 
	return rt;
}
int getnext(int val)//val+1到n最大的数 （将val分离出去） 
{
	int x,y;split(root,val,x,y);
	int now=y;while(tr[now].l) now=tr[now].l;//最小 
	int rt=tr[now].val;root=merge(x,y);//记住要合并 
	return rt;
}
int main()
{
	int t;scanf("%d",&t);
	while(t--)
	{
		int op;scanf("%d",&op);
		if(op==1)
		{
			int x;scanf("%d",&x);
			ins(x);
		}
		else if(op==2)
		{
			int x;scanf("%d",&x);
			dl(x);
		}
		else if(op==3)
		{
			int x;scanf("%d",&x);
			printf("%d\n",getrank(x));
		}
		else if(op==4)
		{
			int x;scanf("%d",&x);
			printf("%d\n",getval(x));
		}
		else if(op==5)
		{
			int x;scanf("%d",&x);
			printf("%d\n",getper(x));
		}
		else 
		{
			int x;scanf("%d",&x);
			printf("%d\n",getnext(x));
		}
	}
	return 0;
}
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

P2234 [HNOI2002]营业额统计明显的我们需要维护比，当前x小的最大值，比当先x大的最小值。

#include
#define int long long 
using namespace std;
int n,m,len=0,root;
struct treap
{
	int siz,val,key,l,r;
};treap tr[1000001];
int btnew(int val)
{
	int now=++len;
	tr[now].val=val;tr[now].key=rand();tr[now].siz=1;
	return now;	
}
void update(int now)
{
	tr[now].siz=tr[tr[now].l].siz+tr[tr[now].r].siz+1;
	return ;
}
void split(int now,int val,int &x,int &y)
{
	if(!now) x=y=0;
	else 
	{
		if(tr[now].val<=val) x=now,split(tr[now].r,val,tr[now].r,y);
		else y=now,split(tr[now].l,val,x,tr[now].l);
	}
	return ; 
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(tr[x].key>tr[y].key)
	{
		tr[x].r=merge(tr[x].r,y);
		update(x);return x;
	}
	else 
	{
		tr[y].l=merge(x,tr[y].l);
		update(y);return y;
	}
}
void ins(int val)
{
	int x,y;split(root,val-1,x,y);
	root=merge(merge(x,btnew(val)),y);
	return ;
}
int getper(int val)
{
	int x,y,z;split(root,val,x,y);
	int now=x;while(tr[now].r) now=tr[now].r;
	int rt=tr[now].val;root=merge(x,y);
	return rt;
}
int getnext(int val)
{
	int x,y,z;split(root,val,x,y);
	int now=y;while(tr[now].l) now=tr[now].l;
	int rt=tr[now].val;root=merge(x,y);
	return rt;
}
signed main()
{
	scanf("%lld",&n);ins(1e18);ins(-1e18);int ans=0;
	for(int i=1;i<=n;i++)
	{
		int x;scanf("%lld",&x);
		if(i==1) ans+=x;
		else ans+=min(x-getper(x),getnext(x)-x);
		ins(x);
	}printf("%lld",ans);
	return 0;
}
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
72
73
74
75

P1486 [NOI2004] 郁闷的出纳员嗯！

#include
#define int long long 
using namespace std;
int n,m,len=0,saygb=0,minn,root;
struct treap 
{
	int siz,val,key,l,r;
};treap tr[3000001];
int btnew(int val)
{
	int now=++len;
	tr[now].val=val,tr[now].key=rand(),tr[now].siz=1;
	return now;
}
void update(int now)
{
	tr[now].siz=tr[tr[now].l].siz+tr[tr[now].r].siz+1;
	return ;
}
void split(int now,int val,int &x,int &y)
{
	if(!now) x=y=0;
	else 
	{
		if(tr[now].val<=val) x=now,split(tr[now].r,val,tr[now].r,y);//明显的tr[now].r
		else y=now,split(tr[now].l,val,x,tr[now].l);
		update(now);
	}
	return ;
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(tr[x].key>tr[y].key)
	{
		tr[x].r=merge(tr[x].r,y);
		update(x);return x;
	}
	else 
	{
		tr[y].l=merge(x,tr[y].l);
		update(y);return y;
	}
}
void ins(int val)
{
	int x,y;split(root,val,x,y);
	root=merge(merge(x,btnew(val)),y);
	return ;
}
int getval(int rank)
{
	int now=root;
	while(now)
	{
		if(tr[tr[now].l].siz+1==rank) break ;
		else if(tr[tr[now].l].siz>=rank) now=tr[now].l;
		else rank-=tr[tr[now].l].siz+1,now=tr[now].r;
	}
	return tr[now].val;
}
void dl(int val)
{
	int x,y,z;split(root,val,x,y);
	root=y;saygb+=tr[x].siz;
	return ;
}
signed main()
{
	scanf("%lld%lld",&n,&minn);int sum=0;
	while(n--)
	{
		char op[10];scanf("%s",op+1);
		if(op[1]=='I')  	
		{
			int x;scanf("%lld",&x);
			if(x>=minn) x-=sum,ins(x);
		}
		else if(op[1]=='A')
		{
			int k;scanf("%lld",&k);sum+=k;
		}
		else if(op[1]=='S')
		{
			int k;scanf("%lld",&k);sum-=k;
			dl(minn-sum-1);
		}
		else 
		{ 
			int x;scanf("%lld",&x);
			if(tr[root].siz>=x) printf("%lld\n",getval(tr[root].siz-x+1)+sum);
			else printf("-1\n");
		}
	}
	printf("%lld",saygb);
	return 0;
}
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

P3850 [TJOI2007]书架排名分裂的好题。练习了一下，哦对提一下，排名分裂与权值分裂是两种分裂方法。我们上面写的都是按照权分裂的，那么这一题不好用按权分裂的方法，于是我们选择排名分裂。那么分裂的时候就要注意了！

#include
using namespace std;
int n,m,len=0,root;
struct treap
{
	int siz,val,key,lc,rc;
};treap tr[1000001];
string s[1000001];
void update(int now)
{
	tr[now].siz=tr[tr[now].lc].siz+tr[tr[now].rc].siz+1;
	return ;
}
int btnew(int val)
{
	int now=++len; 
	tr[now].val=val,tr[now].key=rand(),tr[now].siz=1;
	return now;
}
void split(int now,int siz,int &x,int &y)
{
	if(!now) x=y=0;
	else 
	{
		if(tr[tr[now].lc].siz>=siz) y=now,split(tr[now].lc,siz,x,tr[now].lc);
		else x=now,split(tr[now].rc,siz-tr[tr[now].lc].siz-1,tr[now].rc,y);
		update(now);
	}
	return ;
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(tr[x].key>tr[y].key) 
	{
		tr[x].rc=merge(tr[x].rc,y);
		update(x);return x;
	}
	else 
	{
		tr[y].lc=merge(x,tr[y].lc);
		update(y);return y;
	}
}
void ins(int val,int id)
{
	int x,y;split(root,val,x,y);
	root=merge(merge(x,btnew(id)),y);
	return;
}
void findnum(int val)
{
	int r1,r2,r3,r4;split(root,val,r1,r2);split(r2,1,r3,r4);
	cout<<s[tr[r3].val]<<endl;
	root=merge(r1,merge(r3,r4));
	return ;
}
int main()
{
	scanf("%d",&n);int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cin >> s[++cnt];ins(i-1,cnt);
	}scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		cin >> s[++cnt];int x;scanf("%d",&x);
		ins(x,cnt);
	}int q;scanf("%d",&q);
	while(q--)
	{
		int x;scanf("%d",&x);
		findnum(x);
	}
	return 0;
} 
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
72
73
74
75
76

P3391 【模板】文艺平衡树啊这个其实就维护一个区间，那么我们考虑从lazy入手，那么发现区间反转的操作（其实线段树的操作也一样）就只是交换左右两个儿子。那么再通过一个大小排序维护，即可。

#include
using namespace std;
int n,m,len=0,root=0;
struct treap
{
	int siz,val,key,lc,rc,lazy;
};treap tr[100001];
int btnew(int val)
{
	int now=++len;
	tr[now].siz=1,tr[now].val=val,tr[now].key=rand(),tr[now].lazy=0;
	return now;
}
void update(int now)
{
	tr[now].siz=tr[tr[now].lc].siz+tr[tr[now].rc].siz+1;
	return ;
}
void pushdown(int now)
{
	if(!tr[now].lazy) return ;//printf("*");
	swap(tr[now].lc,tr[now].rc);tr[now].lazy=0;
	tr[tr[now].lc].lazy^=1,tr[tr[now].rc].lazy^=1;
	return ;
}
void split(int now,int siz,int &x,int &y)
{
	if(!now) x=y=0;
	else 
	{
		pushdown(now);
		if(tr[tr[now].lc].siz<siz) x=now,split(tr[now].rc,siz-tr[tr[now].lc].siz-1,tr[now].rc,y);
		else y=now,split(tr[now].lc,siz,x,tr[now].lc);
		update(now);
	}
	return ;
}


int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(tr[x].key>tr[y].key)
	{
		pushdown(x); 
		tr[x].rc=merge(tr[x].rc,y);
		update(x);return x;
	}
	else 
	{
		pushdown(y); 
		tr[y].lc=merge(x,tr[y].lc);
		update(y);return y;
	}  
}
void re(int l,int r)
{ 
	int x,y,z;split(root,l-1,x,y);split(y,r-l+1,y,z);
	tr[y].lazy^=1;root=merge(merge(x,y),z);
	return ;  	
}
void ldr(int now)
{
	if(!now) return ;pushdown(now);
	ldr(tr[now].lc);printf("%d ",tr[now].val);ldr(tr[now].rc);
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) root=merge(root,btnew(i));
	while(m--)
	{
		int l,r;scanf("%d%d",&l,&r);
		re(l,r);
	}
	ldr(root); 
	return 0;
}
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
72
73
74
75
76
77
78
79

P3224 [HNOI2012]永无乡

呃启发式合并确实离谱啊，不过其实大部分的合并题目都应该想到这一个，合并并查集，连通块等东西都可以用这一手。然后因为根的问题调了一会。

#include
using namespace std;
int n,m,len=0;
int root[1000001];
struct treap
{
	int lc,rc,siz,val,key;
};treap tr[1000001];
int findroot(int x)
{
	if(root[x]==x) return x;
	return root[x]=findroot(root[x]);
}
int btnew(int val)
{
	int now=++len;
	tr[now].key=rand(),tr[now].siz=1,tr[now].val=val;
	return now;
}
void update(int now)
{
	tr[now].siz=tr[tr[now].lc].siz+tr[tr[now].rc].siz+1; 
	return ;
}
void split(int now,int val,int &x,int &y)
{
	if(!now) x=y=0;
	else 
	{
		if(tr[now].val<=val) x=now,split(tr[now].rc,val,tr[now].rc,y);
		else y=now,split(tr[now].lc,val,x,tr[now].lc);	
		update(now);
	}
	return ;
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(tr[x].key>tr[y].key) 
	{
		tr[x].rc=merge(tr[x].rc,y);
		update(x);return x;  
	}
	else 
	{
		tr[y].lc=merge(x,tr[y].lc);
		update(y);return y;  
	}
}
int ins(int x,int y)
{
	int a,b,rt;split(x,tr[y].val,a,b);	
	return merge(merge(a,y),b);
}
void dfs(int &x,int y)
{
	if(!y) return ;
	dfs(x,tr[y].lc);dfs(x,tr[y].rc);
	tr[y].lc=tr[y].rc=0;x=ins(x,y);
//	update(x);
	return ;
}
int hb(int x,int y)
{
	if(tr[x].siz<tr[y].siz) swap(x,y);
	dfs(root[x],y);
	return root[x];
}
int getval(int x,int rank)
{	
	int now=x;
	while(now)
	{
		if(tr[tr[now].lc].siz+1==rank) break;
		else if(tr[tr[now].lc].siz>=rank) now=tr[now].lc;
		else rank-=tr[tr[now].lc].siz+1,now=tr[now].rc;
//		printf("<<%d %d\n",now,tr[now].siz);
	}
	return now;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	{
		int x;scanf("%d",&x);
		root[i]=btnew(x);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,fx,fy;scanf("%d%d",&x,&y);fx=findroot(x),fy=findroot(y);
		if(fx==fy) continue ;
		int z=hb(root[x],root[y]);root[fx]=root[fy]=root[z]=z;
	}
	int q;scanf("%d",&q);
	while(q--)
	{
		char op[10];scanf("%s",op+1);
		if(op[1]=='Q')
		{
			int x,rank;scanf("%d%d",&x,&rank);x=findroot(x);
			if(tr[x].siz>=rank) printf("%d\n",getval(x,rank));
			else printf("-1\n");	
		}
		else 	
		{
			int x,y,fx,fy;scanf("%d%d",&x,&y);fx=findroot(x),fy=findroot(y);
			if(fx==fy) continue ;
			int z=hb(root[x],root[y]);root[fx]=root[fy]=root[z]=z;
		}
	}
	return 0;
} 
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

再写一题就开始复习了P2042 [NOI2005] 维护数列，实现起来很麻烦的。维护区间标记啊，反转啊，还要用队列保存可用的节点。尽量写写吧，比较这个专题快结束了。
谈一谈插入，这个插入不简单，nlogn的插入已经被淘汰了！我们直接建树然后再插入就可以达到n的复杂度？据说是按照笛卡尔树的建树方式，不过算了学不来。
那么，拜拜~