【总结】 伸展树Splay

挖坑待补

前言

感觉我在联赛还差4天的时候学习Splay有点慌，但还是要学一下。

定义

我们先对Splay的数组进行一些定义：

struct node{

	int ff,siz,cnt,ch[2],val;

	//ff表示父亲，siz表示子树大小，ch表示儿子，cnt表示与这个点权值相同的点的个数，val表示权值。

}t[N<<2];

操作

我们的Splay应该要支持以下几个操作：

• 插入
• 删除
• 查找排名为k的数
• 查找k的排名
• 查找k的前驱
• 查找k的后继
• 分裂（不会）
• 合并（启发式合并）

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N=500010;

int root,tot;

inline int gi(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

class SplayTree{

private:

	struct node{

		int ff,siz,cnt,ch[2],val;

		//ff表示父亲，siz表示子树大小，ch表示儿子，cnt表示与这个点权值相同的点的个数，val表示权值。

	}t[N<<2];

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

	inline void rotate(int x){

		int y=t[x].ff,z=t[y].ff;

		int k=(x==t[y].ch[1]);

		t[z].ch[y==t[z].ch[1]]=x;

		t[x].ff=z;

		t[y].ch[k]=t[x].ch[k^1];

		t[t[x].ch[k^1]].ff=y;

		t[x].ch[k^1]=y;

		t[y].ff=x;

		pushup(y);pushup(x);

	}

public:

	inline void Splay(int x,int goal){

		while(t[x].ff!=goal){

			int y=t[x].ff,z=t[y].ff;

			if(z!=goal)

				(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);

			rotate(x);

		}

		if(!goal)root=x;

	}

	inline void find(int x){

		int u=root;

		if(!u)return;

		while(t[u].val!=x && t[u].ch[x>t[u].val])

			u=t[u].ch[x>t[u].val];

		Splay(u,0);

	}

	inline void Insert(int x){

		int u=root,ff=0;

		while(u && t[u].val!=x){ff=u;u=t[u].ch[x>t[u].val];}

		if(u)t[u].cnt++;

		else{

			u=++tot;

			t[u].cnt=t[u].siz=1;t[u].val=x;

			t[u].ff=ff;t[u].ch[0]=t[u].ch[1]=0;

			if(ff)t[ff].ch[x>t[ff].val]=u;

		}

		Splay(u,0);

	}

	inline int Next(int x,int f){//f=1表示后继，f=0表示前驱

		find(x);

		int u=root;

		if(t[u].val>x && f)return u;

		if(t[u].val<x && !f)return u;

		u=t[u].ch[f];

		while(t[u].ch[f^1])u=t[u].ch[f^1];

		return u;

	}

	inline void Delete(int x){

		int last=Next(x,0),nxt=Next(x,1);

		Splay(last,0);Splay(nxt,last);

		int del=t[nxt].ch[0];

		if(t[del].cnt>1){t[del].cnt--;Splay(del,0);}

		else t[nxt].ch[0]=0;

	}

	inline int kth(int x){

		int u=root;

		if(t[u].siz<x)return 0;

		while(1){

			int y=t[u].ch[0];

			if(t[y].siz<x && t[y].siz+t[u].cnt>=x)return t[u].val;

			if(t[y].siz>=x)u=y;

			else{

				x-=t[y].siz+t[u].cnt;

				u=t[u].ch[1];

			}

		}

	}

	inline int Val(int u){

		return t[u].val;

	}

	inline int ch0size(){

		return t[t[root].ch[0]].siz;

	}

}Splay;

int main(){

	int n=gi();

	Splay.Insert(2147483647);

	Splay.Insert(-2147483648);

	while(n--){

		int opt=gi(),x=gi();

		if(opt==1)Splay.Insert(x);

		if(opt==2)Splay.Delete(x);

		if(opt==3){

			Splay.find(x);

			printf("%d\n",Splay.ch0size());

		}

		if(opt==4)printf("%d\n",Splay.kth(x+1));

		if(opt==5)printf("%d\n",Splay.Val(Splay.Next(x,0)));

		if(opt==6)printf("%d\n",Splay.Val(Splay.Next(x,1)));

	}

	return 0;

}