郁闷的出纳员

link

约等于平衡树模板题。不知道为什么平衡树似乎总是和我有仇，怎么写怎么错。仅以此篇博客纪念我与平衡树之间的斗争的阶段性胜利。

这道题相当于是要求支持三个操作，插入，查找排名为k的数，删除小于某个值的所有元素。这些都是平衡树的基本操作，第三个只需插入一个那样的节点，把它旋转到根部，如何删除左子树即可。

以上操作似乎SPLAY或者无旋treap要好弄一些，但我还没写过……

#include
#include
#include
//#define zczc
const int N=300010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

int m,n,add,in,root,ans;
char w;

#define lc t[wh].l
#define rc t[wh].r
struct node{
	int l,r,data,sum,num,p;
}t[N<<1];
int cnt;
inline int newone(int val){
	t[++cnt].data=val;t[cnt].num=t[cnt].sum=1;
	t[cnt].p=rand();return cnt;
}
inline void pushup(int wh){
	t[wh].sum=t[lc].sum+t[rc].sum+t[wh].num;
}
inline int zig(int wh){
	int a=wh,b=lc,c=t[lc].r;
	return t[a].l=c,pushup(a),t[b].r=a,pushup(b),b;
}
inline int zag(int wh){
	int a=wh,b=rc,c=t[rc].l;
	return t[a].r=c,pushup(a),t[b].l=a,pushup(b),b;
}
int insert(int wh,int val){
	if(!wh)return newone(val);
	if(t[wh].data==val)return t[wh].num++,t[wh].sum++,wh;
	if(val1)return t[wh].num--,t[wh].sum--,wh;
		if(!lc&&!rc)return 0;
		wh=t[lc].p>t[rc].p?zig(wh):zag(wh);
	}
	if(val'Z')w=getchar();read(in);
		if(w=='I'){
			if(in