Orz

P3369 【模板】普通平衡树

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1;
int n;
struct TreapNode{
	int l[maxn], r[maxn], siz[maxn], rnd[maxn], w[maxn], val[maxn];
	int sz = 0, ans = 0, rt = 0;
	TreapNode() {for(int i = 0; i < maxn; ++i) l[i] = r[i] = siz[i] = rnd[i] = w[i] = val[i] = 0;}
	
	void pushup(int x) {
		siz[x] = siz[l[x]] + siz[r[x]] + w[x];
	}
	
	void lrotate(int &k){
		int t = r[k];
		r[k] = l[t];
		l[t] = k;
		siz[t] = siz[k];
		pushup(k);
		k = t;
	}
	
	void rrotate(int &k){
		int t = l[k];
		l[k] = r[t];
		r[t] = k;
		siz[t] = siz[k];
		pushup(k);
		k = t;
	}
	
	void insert(int &k, int x){
		if(!k){
			sz++;
			k = sz;
			siz[k] = 1;
			w[k] = 1;
			val[k] = x;
			rnd[k] = rand();
			return;
		}
		++siz[k];
		if(val[k] == x) w[k] ++;
		if(val[k] > x) insert(l[k],x);
		if(val[k] < x) insert(r[k],x);
		if(rnd[l[x]] < rnd[k]) lrotate(k);
		if(rnd[r[x]] < rnd[k]) rrotate(k);
	}
	
	bool del(int &k,int x){
		if(!k)return false;
		if(val[k] == x){
			if(w[k] > 1){
				--w[k];
				--siz[k];
				return true;
			}
			if(l[k] ==0 || r[k] == 0){
				k = l[k]  + r[k];
				return true;
			}
			if(rnd[l[k]] < rnd[r[k]]){
				rrotate(k);
				return del(k,x);
			}else{
				lrotate(k);
				return del(k,x);
			}
		}else{
			if(val[k] > x){
				bool succ = del(l[k],x);
				if(succ) --siz[k];
				return succ;
			}else{
				bool succ = del(r[k],x);
				if(succ) --siz[k];
				return succ;
			}
		}
	}
	
	int queryrank(int k, int x){
		if(!k) return 0;
		if(x == val[k]) return (siz[l[k]] + 1);
		if(x < val[k]) return queryrank(l[k],x);
		if(x > val[k]) return (siz[l[k]] + w[k] + queryrank(r[k],x));
	}
	
	int querynum(int k, int x){
		if(!k) return 0;//
		if(x < siz[l[k]]) return querynum(l[k],x);
		else if(x > siz[r[k]] + w[k]) return querynum(r[k],x - siz[r[k]] - w[k]);
		else return val[k];
	}
	
	void querypre(int k, int x){
		if(!k) return;
		if(val[k] < x){
			ans = k;
			querypre(r[k],x);
		}else{
			querypre(l[k],x);
		}
	}
	
	void querysub(int k, int x){
		if(!k) return ;
		if(val[k] > x){
			ans = k;
			querysub(l[k],x);
		}else{
			querysub(r[k],x);
		}
	}
}T;
int main(){
	srand(233);
	cin>>n;
	do{
		int opt, x;
		scanf("%d%d",&opt,&x);
		if(opt == 1){
			T.insert(T.rt, x);
		}
		if(opt == 2){
			T.del(T.rt,x);
		}
		if(opt == 3){
			printf("%d\n",T.querynum(T.rt,x));
		}
		if(opt == 4){
			printf("%d\n",T.queryrank(T.rt,x));
		}
		if(opt == 5){
			T.ans = 0;
			T.querypre(T.rt,x);
			printf("%d\n",T.val[T.ans]);
		}
		if(opt == 6){
			T.ans = 0;
			T.querysub(T.rt,x);
			printf("%d\n",T.val[T.ans]);
		}
	}while(--n);
	return 0;
}