提供一个FHQ-Treap指针版的模版代码

struct Treap{
		struct Treap_Node{
			ll sum,pri;
			int siz;
			Treap_Node* ls;
			Treap_Node* rs;
			Treap_Node(ll _sum) : siz(1), ls(NULL), rs(NULL) { sum=_sum,pri=rand(); }
		};
		Treap_Node* root;
		Treap() : root(NULL) { srand(time(0)); }
		void update(Treap_Node* &rt){
			if (rt->ls == NULL && rt->rs == NULL) rt->siz=1;
			else if (rt->ls == NULL) rt->siz = rt->rs->siz+1;
			else if (rt->rs == NULL) rt->siz = rt->ls->siz+1;
			else rt->siz = rt->ls->siz + rt->rs->siz+1;
		}
		void split(Treap_Node* rt,ll sum,Treap_Node* &sp1,Treap_Node* &sp2){
			if(rt==NULL){
				sp1=NULL,sp2=NULL;
				return;
			}
			if(rt->sum<=sum) sp1=rt,split(rt->rs,sum,rt->rs,sp2);
			else sp2=rt,split(rt->ls,sum,sp1,rt->ls);
			update(rt);
		}
		Treap_Node* merge(Treap_Node* rt1,Treap_Node* rt2){
			if(rt1==NULL&&rt2==NULL) return NULL;
			if(rt1==NULL) return rt2;
			if(rt2==NULL) return rt1;
			if(rt1->pri>rt2->pri){
				rt1->rs=merge(rt1->rs,rt2);
				update(rt1);
				return rt1;
			}else{
				rt2->ls=merge(rt1,rt2->ls);
				update(rt2);
				return rt2;
			}
		}
		void insert(ll sum){
			Treap_Node* lrt=NULL;
			Treap_Node* rrt=NULL;
			split(root,sum,lrt,rrt);
			Treap_Node* newnode=new Treap_Node(sum);
			root=merge(merge(lrt,newnode),rrt);
		}
		void erase(ll sum){
			Treap_Node* lrt=NULL;
			Treap_Node* rrt=NULL;
			Treap_Node* krt=NULL;
			split(root,sum,lrt,rrt);
			split(lrt,sum-1,lrt,krt);
			if(krt!=NULL) krt=merge(krt->ls,krt->rs);
			root=merge(merge(lrt,krt),rrt);
		}
		int rk(ll sum){
			Treap_Node* lrt=NULL;
			Treap_Node* rrt=NULL;
			split(root,sum-1,lrt,rrt);
			int ans=((lrt==NULL)?(0):(lrt->siz))+1;
			root=merge(lrt,rrt);
			return ans;
		}
		Treap_Node* kth(Treap_Node* rt,int k){
			if(rt==NULL||k>rt->siz) throw runtime_error("You can't find kth in the empty tree!");
			int lsiz=0;
			if(rt->ls==NULL) lsiz=0;
			else lsiz=rt->ls->siz;
			if(k==lsiz+1) return rt;
			if(k<=lsiz) return kth(rt->ls,k);
			return kth(rt->rs,k-lsiz-1);
		}
		ll precursor(ll sum){
			Treap_Node* lrt=NULL;
			Treap_Node* rrt=NULL;
			split(root,sum-1,lrt,rrt);
			ll ans=kth(lrt,lrt->siz)->sum;
			root=merge(lrt,rrt);
			return ans;
		}
		ll successor(ll sum){
			Treap_Node* lrt=NULL;
			Treap_Node* rrt=NULL;
			split(root,sum,lrt,rrt);
			ll ans=kth(rrt,1)->sum;
			root=merge(lrt,rrt);
			return ans;
		}
		ll kth(int k){
			return kth(root,k)->sum;
		}
	};