初探treap, 走入平衡树大家族．

平衡树大家族可还行．

参考资料

https://www.cnblogs.com/guoshaoyang/p/11300886.html

https://blog.csdn.net/yandaoqiusheng/article/details/85037548

https://blog.csdn.net/chenxiaoran666/article/details/81391565

普通平衡树

loj 题目链接

洛谷题目链接

　我的代码

基本上是上述一个参考资料简单修改了一点点，以及加上了很多注释．

/*
编号	题目	状态	分数	总时间	内存	代码 / 答案文件	提交者	提交时间
#919994	#104. 普通平衡树  Accepted	100	445 ms	1284 K	C++ 11 / 2.6 K	robot	2020-08-28 8:48:23
 */

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int N=1e5+10;
int siz[N],key[N],cnt[N],rd[N],son[N][2];
int sz,rt;

// 要根据具体题目数据范围调整
const int INF=1e9+7;

// 用自带的rand 　在洛谷上ac了
// 用这个手写的rand 有一个数据TLE了
/*
unsigned int seed;
int rand(){
	return seed=(int) seed * 482711LL % 2147483647;
}
*/

inline void pushup(int x){
	siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];
}

inline void rotate(int &x,int y){
	int o=son[x][y^1];
	son[x][y^1]=son[o][y];
	son[o][y]=x;
	pushup(x);
	pushup(o);
	x=o;
}

void insert(int &p,int x){ 
	if(!p){ p=++sz; siz[p]=cnt[p]=1; key[p]=x; rd[p]=rand(); return; } 
	if(key[p]==x){ cnt[p]++; siz[p]++; return; }
	int d=(x>key[p]);
	insert(son[p][d],x);
	if(rd[p]<rd[son[p][d]]) rotate(p,d^1);
	pushup(p);
}

void delet(int &p,int x){
	if(!p) return;
	if(x!=key[p])  delet(son[p][x>key[p]],x);
	else{
		if(!son[p][0]&&!son[p][1]){
			cnt[p]--; siz[p]--; if(cnt[p]==0) p=0;
		}else if(son[p][0]&&!son[p][1]){
			rotate(p,1); delet(son[p][1],x);
	   	}else if(!son[p][0]&&son[p][1]){
			rotate(p,0); delet(son[p][0],x);
		}else{
			int d=rd[son[p][0]]>rd[son[p][1]];
			rotate(p,d); delet(son[p][d],x);
		}
	}
	pushup(p);
}


int get_rank(int p,int x){
	// 空结点,直接返回
	if(!p) return 0;
	// x=key[p],返回左子树节点数+1
	if(key[p]==x) return siz[son[p][0]]+1;
	// key[p]<x) x位于右子树，左子树个数+结点个数+x在右子树的位置
	if(key[p]<x) return siz[son[p][0]]+cnt[p]+get_rank(son[p][1],x);
	//if(key[p]>x) x位于左子树,直接向左边递归
	return get_rank(son[p][0],x);
}


int find(int p,int x){
	if(!p) return 0;
	if(siz[son[p][0]]>=x)
		return find(son[p][0],x);
	else if(siz[son[p][0]]+cnt[p]<x)
		return find(son[p][1],x-cnt[p]-siz[son[p][0]]);
	else
		return key[p];
}

// 前驱定义为小于ｘ,且最大的数
int pre(int p,int x){
	if(!p) return -INF;
	if(key[p]>=x) return pre(son[p][0],x);
	else return max(key[p],pre(son[p][1],x));
}

// 后继定义为大于ｘ,且最小的数
int suf(int p,int x){
	if(!p) return INF;
	if(key[p]<=x) return suf(son[p][1],x);
	else return min(key[p],suf(son[p][0],x));
}
main(){
	int q=read();while(q--){
		int x=read();
		int y=read();
		switch(x){
			case 1: insert(rt,y); break; 
			case 2: delet(rt,y); break;
			case 3: printf("%d\n",get_rank(rt,y)); break; 
			case 4: printf("%d\n",find(rt,y)); break; 
			case 5: printf("%d\n",pre(rt,y)); break;
			case 6: printf("%d\n",suf(rt,y)); break; 
		}
	}
}