M y splay

#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
using namespace std;
const int N=1e6+10;
int T;
struct Splay_Tree{
	int rt,sz=0;
	int val[N],ch[N][2],fa[N],siz[N],cnt[N];
	void clear(int x){
		ch[x][0]=ch[x][1]=siz[x]=cnt[x]=val[x]=0;
		return;
	}
	int get(int x){
		return ch[fa[x]][1]==x;
	}
	void updata(int x){
		if(x){
			siz[x]=cnt[x];
			if(ch[x][0])siz[x]+=siz[ch[x][0]];
			if(ch[x][1])siz[x]+=siz[ch[x][1]];
		}
		return;
	}
	void rotate(int x){
		int f=fa[x],gf=fa[f],wh=get(x);
		ch[f][wh]=ch[x][wh^1];
		fa[ch[f][wh]]=f;
		ch[x][wh^1]=f;
		fa[f]=x;
		fa[x]=gf;
		if(gf)ch[gf][ch[gf][1]==f]=x;
		updata(f);updata(x);
	}
	void splay(int x){
		for(int f;f=fa[x];rotate(x))
			if(fa[f])rotate((get(f)==get(x))?f:x);
		rt=x;
		return;
	}
	int search(int u,int x){
		while(val[u]!=x){
			if(val[u]>x)
				if(ch[u][0])
					u=ch[u][0];
				else break;
			if(val[u]<x)
				if(ch[u][1])
					u=ch[u][1];
				else break;
		}
		return u;
	}
	void ins(int x){
		if(rt==0){
			sz++;
			ch[sz][0]=ch[sz][1]=fa[sz]=0;
			rt=sz;
			siz[sz]=cnt[sz]=1;
			val[sz]=x;
			return;
		}
		int u=search(rt,x);
		if(val[u]==x){
			cnt[u]++;
			splay(u);
			return;
		}
		val[++sz]=x;
		cnt[sz]=1;
		fa[sz]=u;
		ch[u][x>val[u]]=sz;
		splay(sz);return;
	}
	int rnk(int x){
		int u=search(rt,x);
		splay(u);
		if(val[u]>=x)return siz[ch[u][0]]+1;
		else return siz[ch[u][0]]+cnt[u]+1;
	}
	int kth(int x){
		int u=rt;
		while(true){
			if(ch[u][0]&&x<=siz[ch[u][0]])
				u=ch[u][0];
			else{
				int tmp=(ch[u][0]?siz[ch[u][0]]:0)+cnt[u];
				if(x<=tmp)return val[u];
				x-=tmp;u=ch[u][1];
			}
		} 
	}
	int gmost(int u,int op){
		if(!op)return search(u,(-inf));
		else return search(u,inf);	
	}
	int pre_nxt(int x,int op){
		int u=search(rt,x);
		splay(u);
		if((val[u]<x&&!op)||(val[u]>x&&op))return u;
		else return gmost(ch[u][op],op^1);
	}
	int pre(int x){return val[pre_nxt(x,0)];}
	int nxt(int x){return val[pre_nxt(x,1)];}
	void del(int x){
		int u=search(rt,x);
		if(val[u]!=x)return;
		splay(u);
		if(--cnt[u])return;
		if(!ch[u][0]){
			fa[ch[u][1]]=0;
			rt=ch[u][1];
			clear(u);
		}else{
			fa[ch[u][0]]=0;
			splay(gmost(ch[u][0],1));
			ch[rt][1]=ch[u][1];
			siz[rt]+siz[ch[u][1]];
			if(ch[rt][1])fa[ch[rt][1]]=rt;
			clear(u);
		}
		return;
	}
}Tree;
int main(){
      
}

M y splay

原文：https://www.cnblogs.com/Xxhdjr/p/13767842.html