随用随取的平衡树板子！
目前已实现无旋Treap和Splay。
使用说明及注意事项：
- 使用命名空间+结构体进行封装，使用时只需
jser::Treap或using namespace jser即可。例如：
/*
way 1
*/
using namespace jser;
Treap tree;
/*
way 2
*/
jser::Splay tree;
Treap随机数生成采用random_device和mt19937，在某些评测姬上可能不适用，可以换用rand（注意数据范围）或手写随机数生成器。- 使用数据范围宏定义，在结构体开头有数组大小
N的宏定义，方便大家修改数据范围。 - 多处使用
register，C++17及以上不适用，记得更换。 - 存储数值为
int类，注意是否需要开long long。
功能介绍
void push(int x)加入一个 \(x\) 值。void pop(int x)删除一个 \(x\) 值。int rank(int x)返回 \(x\) 在数列里的排名。int kth(int x)返回在数列中排名为 \(x\) 的数值。int pre(int x)返回数值 \(x\) 在数列中的前驱。如果没有，返回负无穷。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
};
}