Treap模板【玄学】

一个很好玩的Treap模板。

#include <cstdio>#include <algorithm>#include <cstdlib>using namespace std;const int maxx = 100000 + 100;int n,m,num,flag,Ans,x,root;struct Node{    int lc,rc;    int fix,v;    int cnt,size;}T[maxx];inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0') {if(c == '-') f=-1; c=getchar();}    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}    return x*f;}void update(int i){    T[i].size = T[T[i].lc].size + T[T[i].rc].size + T[i].cnt;}void lturn(int &i){    int t = T[i].rc;    T[i].rc = T[t].lc;    T[t].lc = i;    T[t].size = T[i].size;    update(i);    i = t;}void rturn(int &i){    int t = T[i].lc;    T[i].lc = T[t].rc;    T[t].rc = i;    T[t].size = T[i].size;    update(i);    i = t;}void insert(int &i,int x){    if(i == 0){		num++;		i = num;		T[i].size = T[i].cnt = 1;		T[i].v = x;		T[i].fix = rand();		return;    }    T[i].size++;    if(x == T[i].v) T[i].cnt++;    if(x < T[i].v){		insert(T[i].lc,x);		if(T[T[i].lc].fix < T[i].fix) rturn(i);	}    if(x > T[i].v){		insert(T[i].rc,x);		if(T[T[i].rc].fix < T[i].fix) lturn(i);	}}void remove(int &i,int x){    if(i == 0) return;    if(x > T[i].v)		T[i].size--,remove(T[i].rc,x);    if(x < T[i].v)		T[i].size--,remove(T[i].lc,x);    if(x == T[i].v){		if(T[i].cnt > 1){	    	T[i].size--;	    	T[i].cnt--;	    	return;		}		if(T[i].lc*T[i].rc == 0)	    	i = T[i].lc + T[i].rc;		else if(T[T[i].lc].fix < T[T[i].rc].fix)	    	rturn(i),remove(i,x);		else	    	lturn(i),remove(i,x);    }}int Query_rank(int i,int x){    if(i == 0) return 0;    if(T[i].v == x) return T[T[i].lc].size+1;    if(T[i].v > x) return Query_rank(T[i].lc,x);    if(T[i].v < x) return T[T[i].lc].size + T[i].cnt + Query_rank(T[i].rc,x);}int Query_num(int i,int x){    if(i == 0) return 0;    if(x <= T[T[i].lc].size)		return Query_num(T[i].lc,x);    if(x > T[T[i].lc].size + T[i].cnt)		return Query_num(T[i].rc,x-T[T[i].lc].size-T[i].cnt);    else return T[i].v;}void Query_PRo(int i,int x){    if(i == 0) return;    if(T[i].v < x){		Ans = i;		Query_pro(T[i].rc,x);    }    else Query_pro(T[i].lc,x);}void Query_sub(int i,int x){    if(i == 0) return;    if(T[i].v > x){		Ans = i;		Query_sub(T[i].lc,x);    }    else Query_sub(T[i].rc,x);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){		flag = read();		x = read();		switch(flag){			case 1: insert(root,x);break;			case 2: remove(root,x);break;			case 3: printf("%d/n",Query_rank(root,x));break;			case 4: printf("%d/n",Query_num(root,x)); break;			case 5: Ans = 0;Query_pro(root,x);printf("%d/n",T[Ans].v);break;			case 6: Ans = 0;Query_sub(root,x);printf("%d/n",T[Ans].v);break;			default: printf(">.<");break;		}    }    return 0;}