splay入坑

最新推荐文章于 2021-10-12 21:35:35 发布

Hzoi_Anonymity

最新推荐文章于 2021-10-12 21:35:35 发布

阅读量366

点赞数 1

分类专栏： splay 文章标签：平衡树 splay

本文链接：https://blog.csdn.net/H_Anonymity/article/details/76436024

版权

splay 专栏收录该内容

1 篇文章

订阅专栏

1829. [Tyvj 1728]普通平衡树

★★★ 输入文件： phs.in 输出文件： phs.out
时间限制：1 s 内存限制：128 MB

【题目描述】

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

【输入格式】

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

【输出格式】

对于操作3,4,5,6每行输出一个数，表示对应答案

【样例输入】

【样例输出】

106465
84185
492737

【提示】

1.n的数据范围：n<=100000

2.每个数的数据范围：[-1e7,1e7]

写完Treap后写splay，感觉真长，代码高亮看得眼前都绿了...新单词get:Predecessor，Successor。

感谢rvalue的板子.

#include<cstdio>
#include<iostream>
#include<cstring>
#define lch ch[0]
#define rch ch[1]
#define kch ch[k]
#define xch ch[k^1]
const int inf=0x7fffffff;
inline int read()
{	char c=getchar();int x=0,y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
class splay
{
	private:
		struct node
		{	int k,s;
			node* pt;node* ch[2];
			node(const int& key)
			{	this->k=key;this->s=1;
				this->lch=NULL;this->rch=NULL;
			}
			inline int sz(){return this==NULL?0:this->s;}
			inline int key(){return this==NULL?0:this->k;}
			inline void mt(){if(this!=NULL) this->s=this->lch->sz()+this->rch->sz()+1;}
			inline int pos(){return this==this->pt->lch;}
		}*root;
		void rotate(node* root,int k)
		{	node* tmp=root->xch;
			if(root->pt==NULL) this->root=tmp;
			else if(root->pt->lch==root) root->pt->lch=tmp;
			else root->pt->rch=tmp;
			tmp->pt=root->pt;
			root->xch=tmp->kch;
			if(root->xch!=NULL) root->xch->pt=root;
			tmp->kch=root;root->pt=tmp;
			root->mt();tmp->mt();
		}
		void sp(node* root,node* pt=NULL)
		{	while(root->pt!=pt)
			{	int k=root->pos();
				if(root->pt->pt==pt) this->rotate(root->pt,k);
				else
				{	int d=root->pt->pos();
					this->rotate(k==d?root->pt->pt:root->pt,k);
					this->rotate(root->pt,d);
				}
			}
		
		}
	public:
		node* kth(int x)
		{	node* root=this->root;
			while(root!=NULL)
			{	int k=root->lch->sz()+1;
				if(x<k) root=root->lch;
				else if(x==k) return root;
				else x-=k,root=root->rch;
			}
			return NULL;
		}
		int rank(const int& key)
		{	node* root=this->root;
			int rk=1;
			while(root!=NULL)
			{	if(root->key()<key)
					rk+=root->lch->sz()+1,root=root->rch;
				else root=root->lch;
			}
			return rk;
		}
		void insert(const int& key)
		{	int pos=this->rank(key)-1;
			this->sp(this->kth(pos));
			this->sp(this->kth(pos+1),this->root);
			node* tmp=new node(key);
			this->root->rch->lch=tmp;
			tmp->pt=this->root->rch;
			this->root->rch->mt();
			this->root->mt();
		}
		void del(const int& key)
		{	int pos=this->rank(key);
			this->sp(this->kth(pos-1));
			this->sp(this->kth(pos+1),root);
			delete this->root->rch->lch;
			this->root->rch->lch=NULL;
			this->root->rch->mt();
			this->root->mt();
		}
		inline int pre(const int& key){return this->kth(this->rank(key)-1)->key();}
		inline int suc(const int& key){return this->kth(this->rank(key+1))->key();}
		splay()
		{	this->root=new node(-inf);
			this->root->rch=new node(inf);
			this->root->rch->pt=this->root;
			this->root->rch->mt();
			this->root->mt();
		}
};
int main()
{	//freopen("phs.in","r",stdin);
	//freopen("phs.out","w",stdout);
	splay* rt=new splay();
	int t,op,key;
	t=read();
	while(t--)
	{	op=read();key=read();
		if(op==1) rt->insert(key);
		else if(op==2) rt->del(key);
		else if(op==3) printf("%d\n",rt->rank(key)-1);
		else if(op==4) printf("%d\n",rt->kth(key+1)->key());
		else if(op==5) printf("%d\n",rt->pre(key));
		else printf("%d\n",rt->suc(key)); 
	}
	return 0;
}