0分求调，Treap树

#include<bits/stdc++.h>
using namespace std;
struct Treap{
	int l,r;
	int val;
	int size;
	int dat;
}s[100000];

int tot,root;

int New(int value)
{
	s[++tot].val=value;
	s[tot].size=1;
	s[tot].dat=rand();
	return tot;
}

void Printf(int p)
{
	cout<<"************\n";
	cout<<"P: "<<p<<endl;
	cout<<"L: "<<s[p].l<<" R: "<<s[p].r<<endl;
	cout<<"Val: "<<s[p].val<<endl;
	cout<<"Size: "<<s[p].size<<endl;
	cout<<"*************\n";
}

void Build()
{
	New(-2147483647);
	New(2147483647);
	root=1,s[1].r=2;
	s[1].size=2;
}

void Update(int p)
{
	s[p].size=s[s[p].l].size+s[s[p].r].size+1;
	return;
}
void zig(int &p)
{
	int q=s[p].l;
	s[p].l=s[p].r;
	s[q].r=p;
	p=q;
	Update(s[p].r);
	Update(p);
	return;
}

void zag(int &p)
{
	int q=s[p].r;
	s[p].r=s[q].l;
	s[q].l=p;
	p=q;
	Update(s[p].l);
	Update(p);
	return;
}
void Insert(int &p,int val)
{
	if(p==0)
	{
		p=New(val);
		return;
	}
	else if(val<s[p].val)
	{
		Insert(s[p].l,val);
		if(s[p].dat<s[s[p].l].dat)zig(p);
	}
	else 
	{
		Insert(s[p].r,val);
		if(s[p].dat<s[s[p].r].dat)zag(p);
	}
	Update(p);
}

int GetRank(int p,int val)
{

	if(p==0)return 0;
	if(val>s[p].val)
	{
		return s[s[p].l].size+GetRank(s[p].r,val)+1;
	}
	else if(val==s[p].val)
	{
		return s[s[p].l].size+1;
	}
	else if(val<s[p].val)
	{
		return GetRank(s[p].l,val);
	}
}

int GetVal(int p,int rank)
{
	if(p==0)return -1;
	if(s[s[p].l].size>=rank)return GetVal(s[p].l,rank);
	else if(s[s[p].l].size+1>=rank)return s[p].val;
	else return GetVal(s[p].r,rank-s[s[p].l].size-1);
}

int GetPre(int val)
{
	int ans=1;
	int p=root;
	while(p)
	{
		if(val==s[p].val)
		{	
			if(s[p].l)
			{
				p=s[p].l;
				while(s[p].r)p=s[p].r;
				ans=p;
			}
			break;
		}
		if(s[p].val<val&&s[p].val>s[ans].val)ans=p;
		p= val<s[p].val?s[p].l:s[p].r;
	}
	return s[ans].val;
}

int GetNext(int val)
{
	int ans=2;
	int p=root;
	while(p)
	{
		if(val==s[p].val)
		{	
			if(s[p].r)
			{
				p=s[p].r;
				while(s[p].l)p=s[p].l;
				ans=p;
			}
			break;
		}
		if(s[p].val>val&&s[p].val<s[ans].val)ans=p;
		p= val<s[p].val?s[p].l:s[p].r;
	}
	return s[ans].val;
}

int n;

int main()
{
	Build();
	cin>>n;
	int opt,x;
	for(int i=1;i<=n;++i)
	{
		cin>>opt>>x;
		switch(opt)
		{
			case 1:
				cout<<GetRank(root,x)-1<<endl;
				break;
			case 2:
				cout<<GetVal(root,x+1)<<endl;
				break;
			case 3:
				cout<<GetPre(x)<<endl;
				break;
			case 4:
				cout<<GetNext(x)<<endl;
			case 5:
				Insert(root,x);
				break;	
		}		
	}
	return 0;
}