全 WA，求助（Treap 代码是过了模板题的）

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
const int MAXN=100005;
struct Node
{
	int ch[2];
	int size,cnt;
	int rnd,val;
};
Node tree[MAXN<<1];
int n,tot,root;
int newnode(int val)
{
	tot++;
	tree[tot].val=val;
	tree[tot].cnt=1;
	tree[tot].size=1;
	tree[tot].rnd=rand();
	tree[tot].ch[0]=0;
	tree[tot].ch[1]=0;
	return tot;
}
void update(int id)
{
	tree[id].size=tree[tree[id].ch[0]].size+tree[tree[id].ch[1]].size+tree[id].cnt;
}
void rotate(int &id,int k)
{
	int x=tree[id].ch[k];
	tree[id].ch[k]=tree[x].ch[k^1];
	tree[x].ch[k^1]=id;
	update(id);
	update(x);
	id=x;
}
void insert(int &id,int val)
{
	if(!id)
	{
		id=newnode(val);
		return ;
	}
	if(tree[id].val==val)
	{
		tree[id].cnt++;
	}
	else
	{
		int k=val>tree[id].val;
		insert(tree[id].ch[k],val);
		if(tree[id].rnd>tree[tree[id].ch[k]].rnd)
		{
			rotate(id,k);
		}
	}
	update(id);
}
int kth(int id,int k)
{
	if(!id || k<=0 || tree[id].size<k)
	{ 
		return 0;
	}
	int lsize=tree[tree[id].ch[0]].size;
	if(k<=lsize)
	{
		return kth(tree[id].ch[0],k);
	}
	else if(k>lsize+tree[id].cnt)
	{
		return kth(tree[id].ch[1],k-lsize-tree[id].cnt);
	}
	else
	{
		return tree[id].val;
	}
}
void output(int n)
{
	for(int i=0;i<=tot;i++)
	{
		cout<<"node no. "<<i<<":\t( val:"<<tree[i].val<<" cnt:"<<tree[i].cnt<<" rnd:"<<tree[i].rnd<<" size:"<<tree[i].size<<" lson:"<<tree[i].ch[0]<<" rson:"<<tree[i].ch[1]<<")"<<endl;
	}
	cout<<endl;
}
int main()
{
//	srand(time(0));
	int m,val;
	scanf("%d",&n);
	int root=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&val);
		insert(root,val);
//		output(root);
	}
	scanf("%d",&m);
	char opt[10];
	for(int i=1;i<=m;i++)
	{
		scanf("%s",opt);
		if(opt[0]=='m')
		{
//			cout<<kth(root,tot/2+1)<<" ";
			if(!(tot%2))
			{
				printf("%d\n",kth(root,tot/2));
			}
			else
			{
				printf("%d\n",kth(root,tot/2+1));
			}
		}
		else if(opt[0]=='a')
		{
			scanf("%d",&val);
			insert(root,val);
		}
	}
	return 0;
 }