瓜瓜头条

随用随取的无旋Treap板子！

2024-08-13 16:20 由 一位很会的教授er~ 发表于 #后端开发

使用说明及注意事项：

  1. 使用命名空间+结构体进行封装，使用时只需jser::Treap或using namespace jser即可。例如：
/*
way 1
*/
using namespace jser;
Treap tree;
/*
way 2
*/
jser::Treap tree;
  1. 随机数生成采用random_device和mt19937，在某些评测姬上可能不适用，可以换用rand（注意数据范围）或手写随机数生成器。
  2. 使用数据范围宏定义，在结构体开头有数组大小N的宏定义，方便大家修改数据范围。
  3. 多处使用register，C++17及以上不适用，记得更换。
  4. 存储数值为int类，注意是否需要开long long。

功能介绍

  1. void push(int x)加入一个 \(x\) 值。
  2. void pop(int x)删除一个 \(x\) 值。
  3. int rank(int x)返回 \(x\) 在数列里的排名。
  4. int kth(int x)返回在数列中排名为 \(x\) 的数值。
  5. int pre(int x)返回数值 \(x\) 在数列中的前驱。如果没有，返回负无穷。
  6. int next(int x)返回数值 \(x\) 在数列中的后继。如果没有，返回正无穷。

代码时刻

教授の全局宏定义（不喜可换）：

#define il inline
#define ri register int
#define inf 0x3f3f3f3f

正片：

namespace jser
{
	random_device rd;
	long long sed=rd();
	mt19937 rad(time((time_t*)&sed));
	il long long getrand(long long x,long long y)
	{
		return rad()%(y-x+1)+x;
	}
	struct Treap
	{
		#define N 200002
		int root,cnt;
		int val[N],siz[N],pri[N],lson[N],rson[N];
		il void pushup(int x)
		{
			siz[x]=siz[lson[x]]+siz[rson[x]]+1;
		}
		il int merge(int x,int y)
		{
			if(!x||!y)
			{
				return x|y;
			}
			if(pri[x]<pri[y])
			{
				rson[x]=merge(rson[x],y);
				pushup(x);
				return x;
			}
			else
			{
				lson[y]=merge(x,lson[y]);
				pushup(y);
				return y;
			}
		}
		il pair<int,int>split(int x,int y)
		{
			if(!x)
			{
				return {0,0};
			}
			ri ls=lson[x],rs=rson[x];
			if(y==siz[ls])
			{
				lson[x]=0;
				pushup(x);
				return {ls,x};
			}
			if(y==siz[ls]+1)
			{
				rson[x]=0;
				pushup(x);
				return {x,rs};
			}
			pair<int,int>rn;
			if(y<siz[ls])
			{
				rn=split(ls,y);
				lson[x]=rn.second;
				pushup(x);
				return {rn.first,x};
			}
			else
			{
				rn=split(rs,y-siz[ls]-1);
				rson[x]=rn.first;
				pushup(x);
				return {x,rn.second};
			}
		}
		il int rank(int x)
		{
			ri y=root,rn=inf,z=0;
			while(y)
			{
				if(x==val[y])
				{
					rn=min(rn,z+siz[lson[y]]+1);
				}
				if(x<=val[y])
				{
					y=lson[y];
				}
				else
				{
					z+=siz[lson[y]]+1;
					y=rson[y];
				}
			}
			if(rn==inf)
			{
				return z;
			}
			return rn;
		}
		il int kth(int x)
		{
			ri y=root;
			while(1)
			{
				if(siz[lson[y]]==x-1)
				{
					return val[y];
				}
				if(siz[lson[y]]>x-1)
				{
					y=lson[y];
				}
				else
				{
					x-=siz[lson[y]]+1;
					y=rson[y];
				}
			}
		}
		il int pre(int x)
		{
			ri y=root,rn=-inf;
			while(y)
			{
				if(val[y]<x)
				{
					rn=val[y];
					y=rson[y];
				}
				else
				{
					y=lson[y];
				}
			}
			return rn;
		}
		il int next(int x)
		{
			ri y=root,rn=inf;
			while(y)
			{
				if(val[y]>x)
				{
					rn=val[y];
					y=lson[y];
				}
				else
				{
					y=rson[y];
				}
			}
			return rn;
		}
		il void push(int x)
		{
			ri y,rks=rank(x);
			pair<int,int>qwer=split(root,rks);
			cnt++;
			y=cnt;
			val[y]=x;
			pri[y]=rad();
			siz[y]=1;
			root=merge(qwer.first,cnt);
			root=merge(root,qwer.second);
		}
		il void pop(int x)
		{
			ri rks=rank(x);
			pair<int,int>q=split(root,rks),p;
			p=split(q.first,rks-1);
			root=merge(p.first,q.second);
		}
		#undef N
	};
}

热门相关：最强神话帝皇   明天和意外   学霸，你女朋友掉了   梦蝶   全民女神之重生腹黑千金