treap初步，建树，更新，旋转，插入，删除操作

//建树

 struct data{
 	int l,r,v,size,rnd,w;
 }tr[100005];
 

int n,size,root,ans;

void update(int k){
	tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w; 
} 

单旋

void rturn(int &k){
	int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;
	tr[t].size=tr[k].size;update(k);k=t;
}

void lturn(int &k){
   int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;
   tr[t].size=tr[k].size;update(k);k=t;
}

双旋

srand(19268075);

treap的插入：

void insert(int &k,int x){
	if (k==0){//插入到一个空节点 
		size++;k=size; 
		tr[k].size=tr[k].w=1;
		tr[k].v=x;tr[k].rnd=rand();
		return;
	}
	tr[k].size++;
	if (tr[k].v==x) tr[k].v++;
	else if (x>tr[k].v)
	{
		insert(tr[k].r,x);
		if (tr[tr[k].r].rnd<tr[k].rnd)lturn(k);
		
	 } 
	 else {
	 	insert(tr[k].l,x);
	 	if (tr[tr[k].l].rnd<tr[k].rnd) rturn(k); //维护堆性质 
	 }
}

treap的删除：
和普通的BST删除是一样：
如果sh值小于当前值，则递归至左儿子；大于则递归至右儿子
若当前节点数值的出现次数大于1，则减一（通常将一个权值缩掉）

void del(int &k,int x){
	if (k==0) return;
    if (tr[k])//此处有误 
    {
	if (tr[k].w>1)
	{
		tr[k].w--;tr[k].size--;return;
	}
	if (tr[k].l*tr[k].r==0) k=tr[k].l+tr[k].r;
	else if (tr[tr[k].l].rnd<tr[tr[k]].rnd)
	   rturn (k),del(k,x);
	else lturn(k),del(k,x);
   }
   else if (x>tr[k].v)
      tr[k].size--,del(tr[k].r,x);
   else tr[k].size--,del(tr[k].l,x); 
}