RT，模板题求调。

弱省弱校小菜鸡自学平衡树，查不出错，样例过不去。QWQ

自查一整天无果。

//Treap普通平衡树（P3369） 
#include<bits/stdc++.h>
using namespace std;
//一个我并不想看到的快读 
inline int read(){
	int x=0,f=1;
	char c;
	for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
int n,op,x;
namespace Treap{
	class node{
	public:
		int val;//BST维护的权值 
		int rd;//在堆中的优先级 
		int l,r;//左右子树的下标 
		int size;// 以该节点为根的子树大小 
		int cnt;//节点出现次数 
	}a[100009];
	int tot,root;
	//利用子节点更新父节点
	void pushup(int p){
		a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt; 
	} 
	//创建节点并返回节点编号
	int create(int x){
		a[++tot].val=x;
		a[tot].rd=rand();//随机权值，rp++ 
		a[tot].size=a[tot].cnt=1;
		return tot;
	} 
	//右旋
	int zig(int &p){
		int q=a[p].l;
		a[p].l=a[q].r,a[q].r=p,p=q;
		pushup(a[p].r),pushup(p);
	}
	//左旋 
	int zag(int &p){
		int q=a[p].r;
		a[p].r=a[q].l,a[q].r=p,p=q;
		pushup(a[p].l),pushup(p);
	}
	//建树（给定两个边界节点，形成BST，同时维护堆的性质 
	void build(){
		create(-0x7fffffff),create(0x7fffffff);
		root=1,a[1].r=2;
		pushup(root);
		if(a[2].rd>a[1].rd)zag(root);//判断是否满足大根堆的性质，如果不满足则左旋
	}
	//插入
	void insert(int &p,int x){
//		cerr<<"here is insert(op=1)\tp="<<p<<"\tx="<<x<<endl; 
		if(p==0)p=create(x);//如果发现了可以挂x的位置，可能是某个叶子节点的做或者右，挂上去 
		else if(x==a[p].val)a[p].cnt++;
        //【ERROR START】
		else if(x<a[p].val){
			insert(a[p].l,x);
			if(a[a[p].l].rd>a[p].rd)zig(p);//判断是否满足大根堆的性质，如果不满足则右旋		
		}else if(x>a[p].val){
			insert(a[p].r,x);
			if(a[a[p].r].rd>a[p].rd)zag(p);//判断是否满足大根堆的性质，如果不满足则左旋		
		} //【ERROR END】
		pushup(p); 
	} 
	//删除
	void remove(int &p,int x){
		if(p==0)return;//如果没找到x，则直接返回
		if(x==a[p].val){//当前节点就是要删除的x
			if(a[p].cnt>1)a[p].cnt--;
			else{
				if(a[p].l||a[p].r){//不是叶子
					if(!a[p].r||a[a[p].l].rd>a[a[p].r].rd){//如果没有左子树或左子树优先级大于右子树的优先级 
						zig(p),remove(a[p].r,x);
					}else zag(p),remove(a[p].l,x);
				}else p=0;
			}
		}else if(x<a[p].val)remove(a[p].l,x);
		else if(x>a[p].val)remove(a[p].r,x);
		pushup(p);
	} 
	//查询值为x的排名
	int getrank(int p,int x){
		if(p==0)return 0;//没有找到
		if(x==a[p].val)return a[a[p].l].size+1;
		else if(x<a[p].val)return getrank(a[p].l,x);
		else return a[a[p].l].size+a[p].cnt+getrank(a[p].r,x); 
	} 
	//查询排名为x的值
	int getnum(int p,int rank){
		if(p==0)return 0x7fffffff;//没有找到（排名太大）
		if(rank<=a[a[p].l].size)return getnum(a[p].l,rank);
		else if(rank<=a[a[p].r].size+a[p].cnt)return a[p].val;
		else return getnum(a[p].r,rank-a[a[p].l].size-a[p].cnt);
	} 
	//找前驱
	int prev(int p,int x){
		if(p==0)return -0x7fffffff;//没有找到
		if(x<=a[p].val)return prev(a[p].l,x);
		else return max(a[p].val,prev(a[p].r,x));
	}
	//找后继
	int ne(int p,int x){
		if(p==0)return 0x7fffffff;//没有找到
		if(x>=a[p].val)return ne(a[p].r,x);
		else return min(a[p].val,ne(a[p].l,x));
	}
};
int main(){
	Treap::build();
	for(n=read();n--;){
		op=read(),x=read();
		switch(op){
			case 1:Treap::insert(Treap::root,x);break;
			case 2:Treap::remove(Treap::root,x);break;
			case 3:printf("%d\n",Treap::getrank(Treap::root,x)-1);break;
			case 4:printf("%d\n",Treap::getnum(Treap::root,x+1));break;
			case 5:printf("%d\n",Treap::prev(Treap::root,x));break;
			case 6:printf("%d\n",Treap::ne(Treap::root,x));break;
		}
	}
}

谢谢好心人^_^

sto %%% dalao %%% orz