记录编号	537883	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.353 s
提交时间	2019-07-17 22:17:16	内存使用	15.57 MiB

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (t[x].ch[0])
#define rs(x) (t[x].ch[1])
const int N=1e5+7;
int n,cnt;
struct node
{
	int ch[2],pri,val,size;
} t[N];
void push_up(int x){t[x].size=t[ls(x)].size+t[rs(x)].size+1;}
int new_node(int x){t[++cnt].val=x;t[cnt].pri=rand();t[cnt].size=1;return cnt;}
int merge(int x,int y)
{
	if (!x||!y) return x+y;
	if  (t[x].pri<t[y].pri){rs(x)=merge(rs(x),y);push_up(x);return x;}
	else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}
void split(int now,int k,int &x,int &y)
{
	if (!now) x=0,y=0;
	else
	{
		if (t[now].val<=k) x=now,split(rs(now),k,rs(now),y);
		else y=now,split(ls(now),k,x,ls(now));
		push_up(now);
	}
	
}
int k_th(int now,int k)
{
	while (true)
	{
		if (k<=t[ls(now)].size) now=ls(now);
		else if (k==t[ls(now)].size+1) return now;
		else k-=t[ls(now)].size+1,now=rs(now);
	}
}
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	srand((unsigned)time(NULL));
	int Q;scanf("%d",&Q);int root=0,opt,a,x,y,z;
	while (Q--)
	{
		scanf("%d%d",&opt,&a);
		if (opt==1) {split(root,a,x,y);root=merge(merge(x,new_node(a)),y);}
		else if (opt==2) {split(root,a,x,z);split(x,a-1,x,y);y=merge(ls(y),rs(y));root=merge(merge(x,y),z);}
		else if (opt==3) {split(root,a-1,x,y);printf("%d\n",t[x].size+1);merge(x,y);}
		else if (opt==4) {printf("%d\n",t[k_th(root,a)].val);}
		else if (opt==5) {split(root,a-1,x,y);printf("%d\n",t[k_th(x,t[x].size)].val);merge(x,y);}
		else if (opt==6) {split(root,a,x,y);printf("%d\n",t[k_th(y,1)].val);merge(x,y);}
	}
	return 0;
}