随用随取的无旋Treap板子!

教授の世界 2024-08-13 16:39:00 阅读 52

使用说明及注意事项:

  1. 使用命名空间+结构体进行封装,使用时只需<code>jser::Treap或using namespace jser即可。例如:

/*

way 1

*/

using namespace jser;

Treap tree;

/*

way 2

*/

jser::Treap tree;

  1. 随机数生成采用<code>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

};

}


上一篇: java byte数组转String

下一篇: 【C++】4.类和对象(2)

本文标签

干货   


声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。