splay

https://blog.csdn.net/clove_unique/article/details/50636361

treap

思维纲要：https://mubu.com/doc/w10-lxTDU0

what's heap in treap?

assign a random number to any new node in order to prevent its complexity from degenerating due to a sequence of ordered numbers to be inserted

how to make heap?

everytime we insert or delete, just keep the randomly assigned number in heap's order

//reference:https://blog.csdn.net/Emm_Titan/article/details/103246344

#include <bits/stdc++.h>	
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e6+10;//larger
int num=0;//the number of the nodes
int cnt[maxn];//the number of this node
int key[maxn];//value
int ran[maxn];//random value,               and we declare that the deeper the tree, the larger the node's ran'value will be
int siz[maxn];//the number of its sons
int son[maxn][2];//left right son
void pushup(int x)
{
	siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];
}
void rotate(int &x,int op)//mark op=0,1-->left right rotate    
{
	int p=son[x][!op];//save the heir
	son[x][!op]=son[p][op];
	son[p][op]=x;
	pushup(x);//pushup the new son first
	pushup(p);
	x=p;//                               that's cool,because we also need to update the new node(new father)'s father,so we say p is the new x(p succeed x).and because "rotate" always company with "insert(son[k][op],x);" etc., so son[k][op] can be update。 
}							
void my_insert(int &k,int x)//&k:when successfully insert a new node,update it after recursion
{
	if (k==0)
	{
		k=++num;		
		cnt[k]=1;
		key[k]=x;
		ran[k]=rand();
		siz[k]=1;
		return;
	}
	else if (key[k]==x)
	{
		cnt[k]++;
		siz[k]++;
		return;
	}
	int op=(x>key[k]);//to its left right son
	my_insert(son[k][op],x);
	if (ran[son[k][op]]<ran[k]) rotate(k,!op);//rotate from the the other size
	pushup(k);	
}
void my_delete(int &k,int x)
{
	if (k==0) return;//this "x" does not exist
	if (x!=key[k])
	{
		int op=(x>key[k]);
		my_delete(son[k][op],x);
		pushup(k);
		/* TODO (#4#): no matter what, all need to pushup */
		
		return;
	}
	//if x==key[k]----means we get it
	if (cnt[k]>1)
	{
		cnt[k]--;
		siz[k]--;
		pushup(k);
		/* TODO (#2#): forget to pushup */
				
		return;
	}
	if (!son[k][0]&&son[k][1])
	{
		rotate(k,0);//only have right son,so we can only choose left rotate 
		my_delete(son[k][0],x);
	}
	else if (son[k][0]&&!son[k][1])
	{
		rotate(k,1);
		my_delete(son[k][1],x);		
	}
	else if (!son[k][0]&&!son[k][1])
	{
		cnt[k]--;
		siz[k]--;
		if (cnt[k]==0) k=0;
		/* TODO (#3#): directly delete whole note */
		
	}
	else
	{
		int op=(ran[son[k][0]]>ran[son[k][1]]);//if left son's ran'val is larger,we can only choose left rotate,or we break the ran'val rule
		rotate(k,!op);
		my_delete(son[k][!op],x);	
			/* TODO (#1#): (!)op */	
					
	}
	pushup(k);	
}
int my_find(int k,int x)//find key whose rank is x
{
	if (k==0) return 0;
	if (siz[son[k][0]]>=x) return my_find(son[k][0],x);
	else if (siz[son[k][0]]+cnt[k]<x)return my_find(son[k][1],x-siz[son[k][0]]-cnt[k]);
	else return key[k];
}
int my_rank(int k,int x)//find the key's rank
{
	if (k==0) return 0;
	if (key[k]==x) return siz[son[k][0]]+1;
	if (key[k]>x) return my_rank(son[k][0],x);
	return siz[son[k][0]]+cnt[k]+my_rank(son[k][1],x);
}
int my_lowerbound(int k,int x)
{
	if (k==0) return -inf;
	if (key[k]>=x) return my_lowerbound(son[k][0],x);
	else return max(key[k],my_lowerbound(son[k][1],x));
}
int my_upperbound(int k,int x)
{
	if (k==0) return inf;
	if (key[k]<=x) return my_upperbound(son[k][1],x);
	else return min(key[k],my_upperbound(son[k][0],x));
}
int main()
{
//	freopen("t.txt","r",stdin);
	int n;
	cin>>n;
	memset(son,0,sizeof(son));
	int root=0;
	while (n--)
	{
		int opt,x;
		scanf("%d%d",&opt,&x);
		switch(opt)
		{
			case 1:my_insert(root,x);break;
			case 2:my_delete(root,x);break;
			case 3:printf("%d\n",my_rank(root,x));break;
			case 4:printf("%d\n",my_find(root,x));break;
			case 5:printf("%d\n",my_lowerbound(root,x));break;
			case 6:printf("%d\n",my_upperbound(root,x));break;
			default:break;
		}
	}	
//	fclose(stdin);
	return 0;

}