trie树

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


rnd//堆的随机权值
 
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 insert(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].w++;
   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); 
	 }
     
}