其实\(\mathrm{Treap}\)最难的还是rotate函数

• 把问题简化，其实就是处理当前节点的后两代子孙，两条边的问题

  1. root->root_grandson
  2. root_son->root

  就这两步修改

• 然后因为进行第一步时，root对应的那个儿子会被grandson覆盖掉，所以要用一个tmp将son存下来

• 然后先将原本的root更新了，再将引用的root指针传给tmp,再将tmp更新即可，其他的insert和erese结合代码都很易懂

不过\(\mathrm{Treap}\)最重要的是不同的函数运用，这个就结合具体题目而言了

#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<climits>

const int maxn=1e5+2;

struct BT
{
	struct Node
	{
		int v,idx,sz;
		Node* son[2];
		
		void update()
		{
			sz=1;
			
			if( son[0] ) sz+=son[0]->sz;
			if( son[1] ) sz+=son[1]->sz;return;
		}
	}Tree[maxn],*now=Tree;
	
	void rotate(Node* &r,int d)
	{
		Node* tmp=r->son[d^1];
		r->son[d^1]=r->son[d^1]->son[d],tmp->son[d]=r;
		
		r->update();
		r=tmp,tmp->update();return;
	}
	
	void insert(Node* &r,int v)
	{
		if(!r)
		{
			r=now++;
			r->v=v,r->idx=rand(),r->son[0]=r->son[1]=NULL,r->sz=1;return;
		}
		
		int d=( v>r->v );
		insert(r->son[d],v);
		
		r->update();
		
		if( r->idx > r->son[d]->idx ) rotate(r,d^1);
	}
	
	void del(Node* &r,int v)
	{
		if(!r) return;
		
		if( r->v==v )
		{
			if( !r->son[0] and !r->son[1] ) r=NULL;
			else if( !r->son[0] xor !r->son[1] )
			{
				int d=(r->son[1]!=NULL);
				r=r->son[d];
			}
			else
			{
				int d=( r->son[0]->idx < r->son[1]->idx );
				rotate(r,d),del(r->son[d],v);
				
				r->update();
			}return;
		}
		
		int d=( v>r->v );
		del(r->son[d],v),r->update();
	}
	
	int num_search(Node* r,int v)
	{
		if(!r) return 1;
		
		if( v>r->v ) return ( (r->son[0]!=NULL)?r->son[0]->sz:0 ) + 1 + num_search(r->son[1],v);
		else return num_search(r->son[0],v);
	}
	
	int rank_search(Node* r,int v)
	{
		int lsz=( r->son[0]!=NULL?r->son[0]->sz:0 );
		
		if( v==lsz+1 ) return r->v;
		else if( v>lsz ) return rank_search(r->son[1],v-lsz-1);
		else return rank_search(r->son[0],v);
	}
	
	int pre(Node* r,int v)
	{
		if(!r) return INT_MAX;
		
		if(r->v>=v) return pre(r->son[0],v);
		else
		{
			int res=pre(r->son[1],v);
			return ( res!=INT_MAX?res:r->v );
		}
	}
	
	int suf(Node* r,int v)
	{
		if(!r) return INT_MAX;
		
		if(r->v<=v) return suf(r->son[1],v);
		else
		{
			int res=suf(r->son[0],v);
			return ( res!=INT_MAX?res:r->v );
		}
	}
}bt;

int main()
{
	srand(time(0));
	BT::Node* r=NULL;
	
	int n;scanf("%d",&n);
	
	while(n--)
	{
		int op,x;scanf("%d",&op);
		
		if(op==1)
		{
			scanf("%d",&x);
			bt.insert(r,x);
		}
		if(op==2)
		{
			scanf("%d",&x);
			bt.del(r,x);
		}
		if(op==3)
		{
			scanf("%d",&x);
			printf("%d\n",bt.num_search(r,x));
		}
		if(op==4)
		{
			scanf("%d",&x);
			printf("%d\n",bt.rank_search(r,x));
		}
		if(op==5)
		{
			scanf("%d",&x);
			printf("%d\n",bt.pre(r,x));
		}
		if(op==6)
		{
			scanf("%d",&x);
			printf("%d\n",bt.suf(r,x));
		}
	}
	
	return 0;
}