「模板」「讲解」Treap名次树

Treap实现名次树

<题目链接>

---

前言

简介

名次树

节点数据结构

struct node

{

	int v,p,size,c[2];

};//键值，优先级，（包括自身在内的）子树大小，左右子节点。

操作

插入

void Rotate(int &i,bool p)

{

	int t=s[i].c[!p];

	s[i].c[!p]=s[t].c[p],s[t].c[p]=i;

	Update(i),Update(i=t);

}

void Update(int i)

{

	s[i].size=s[s[i].c[0]].size+s[s[i].c[1]].size+1;

}

void Insert(int &i,int x)

{

	if(!i)

	{

		s[i=++cnt].v=x,s[i].p=Random(),s[i].size=1;

		return;

	}

	++s[i].size;

	bool t=x>s[i].v;

	Insert(s[i].c[t],x);

	if(s[s[i].c[t]].p>s[i].p)

		Rotate(i,!t);

}

删除

void Erase(int &i,int x)

{

	if(x==s[i].v)

		if(s[i].c[0] && s[i].c[1])

		{

			bool t=s[s[i].c[0]].p>s[s[i].c[1]].p;

			Rotate(i,t),Erase(s[i].c[t],x);

		}

		else

		{

			i=s[i].c[0]|s[i].c[1];

			return;

		}

	else

		Erase(s[i].c[x>s[i].v],x);

	Update(i);

}

查找排名

int Rank(int i,int x)

{

	return i ? (x>s[i].v ? Rank(s[i].c[1],x)+s[s[i].c[0]].size+1 : Rank(s[i].c[0],x)) : 1;

}

查找排名为x的数

int Xth(int i,int x)

{

	int t=s[s[i].c[0]].size+1;

	if(x<t)

		return Xth(s[i].c[0],x);

	else if(x>t)

		return Xth(s[i].c[1],x-t);

	else

		return s[i].v;

}

查找前驱

int Pre(int i,int x)

{

	return i ? (x>s[i].v ? max(Pre(s[i].c[1],x),s[i].v) : Pre(s[i].c[0],x)) : -INF;

}

查找后继

整体代码

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

using namespace std;

const int MAXN=100010,INF=10000010;

int n;

class Treap

{

	public:

		int rt;

		Treap(void)

		{

			rt=cnt=0;

			memset(a,0,sizeof a);

			memset(s,0,sizeof s);

		}

		void Insert(int &i,int x)

		{

			if(!i)

			{

				s[i=++cnt].v=x,s[i].p=Random(),s[i].size=1;

				return;

			}

			++s[i].size;

			bool t=x>s[i].v;

			Insert(s[i].c[t],x);

			if(s[s[i].c[t]].p>s[i].p)

				Rotate(i,!t);

		}

		void Erase(int &i,int x)

		{

			if(x==s[i].v)

				if(s[i].c[0] && s[i].c[1])

				{

					bool t=s[s[i].c[0]].p>s[s[i].c[1]].p;

					Rotate(i,t),Erase(s[i].c[t],x);

				}

				else

				{

					i=s[i].c[0]|s[i].c[1];

					return;

				}

			else

				Erase(s[i].c[x>s[i].v],x);

			Update(i);

		}

		int Rank(int i,int x)

		{

			return i ? (x>s[i].v ? Rank(s[i].c[1],x)+s[s[i].c[0]].size+1 : Rank(s[i].c[0],x)) : 1;

		}

		int Xth(int i,int x)

		{

			int t=s[s[i].c[0]].size+1;

			if(x<t)

				return Xth(s[i].c[0],x);

			else if(x>t)

				return Xth(s[i].c[1],x-t);

			else

				return s[i].v;

		}

		int Pre(int i,int x)

		{

			return i ? (x>s[i].v ? max(Pre(s[i].c[1],x),s[i].v) : Pre(s[i].c[0],x)) : -INF;

		}

		int Next(int i,int x)

		{

			return i ? (x<s[i].v ? min(Next(s[i].c[0],x),s[i].v) : Next(s[i].c[1],x)) : INF;

		}

	private:

		bool a[MAXN];

		int cnt;

		struct node

		{

			int v,p,size,c[2];

		}s[MAXN];

		int Random(void)

		{

			int x;

			while(a[x=rand()%MAXN]);

			a[x]=1;

			return x;

		}

		void Update(int i)

		{

			s[i].size=s[s[i].c[0]].size+s[s[i].c[1]].size+1;

		}

		void Rotate(int &i,bool p)

		{

			int t=s[i].c[!p];

			s[i].c[!p]=s[t].c[p],s[t].c[p]=i;

			Update(i),Update(i=t);

		}

}T;

int main(int argc,char *argv[])

{

	scanf("%d",&n);

	srand((unsigned)time(NULL));

	for(int i=1,&rt=T.rt,opt,x;i<=n;++i)

	{

		scanf("%d %d",&opt,&x);

		switch(opt)

		{

			case 1:

				T.Insert(rt,x);

				break;

			case 2:

				T.Erase(rt,x);

				break;

			case 3:

				printf("%d\n",T.Rank(rt,x));

				break;

			case 4:

				printf("%d\n",T.Xth(rt,x));

				break;

			case 5:

				printf("%d\n",T.Pre(rt,x));

				break;

			case 6:

				printf("%d\n",T.Next(rt,x));

				break;

		}

	}

	return 0;

}

结束语