题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3224
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
题解1：
Treap模板题。
由于普通二叉搜索树容易退化成链状，考虑到在随机数据下产生的BST是趋*衡树的，因此Treap就是用“随机”来创造平衡条件。
在原来BST的基础上，我们可以对树上所有节点都另外增加一个随机生成的权值 $dat$，迫使整棵BST对于 $dat$ 满足“堆性质”。
在Splay的学习中我们已经知道，右旋zig和左旋zag是不会影响BST的“BST性质”的，而通过zig和zag我们正好又可以达到交换父子节点位置的目的，
因此，我们可以参照二叉堆，如果父子两节点不满足堆性质，则用zig或者zag交换两者位置，从而迫使整棵树满足关于 $dat$ 的“堆性质”。
正是由于这颗二叉树，键值 $key$ 满足BST性质，另一个权值 $dat$ 满足堆性质，因此用单词 tree 和 heap 构成了该数据结构的名称 treap。
AC代码（Treap）：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
const int maxn=1e5+; /******************************** Treap - st ********************************/
int root,nodecnt;
int ch[maxn][];
int key[maxn],dat[maxn];
int cnt[maxn],siz[maxn];
int NewNode(int val)
{
int x=++nodecnt;
key[x]=val; dat[x]=rand();
cnt[x]=siz[x]=;
ch[x][]=ch[x][]=;
return x;
}
void Pushup(int x)
{
siz[x]=siz[ch[x][]]+siz[ch[x][]]+cnt[x];
}
void Init()
{
root=nodecnt=;
key[]=dat[]=;
cnt[]=siz[]=;
ch[][]=ch[][]=;
}
void Build()
{
Init();
NewNode(-INF);
NewNode(INF);
ch[root=][]=;
Pushup(root);
}
void zig(int &x)
{
int lc=ch[x][];
ch[x][]=ch[lc][], ch[lc][]=x, x=lc;
Pushup(ch[x][]), Pushup(x);
}
void zag(int &x)
{
int rc=ch[x][];
ch[x][]=ch[rc][], ch[rc][]=x, x=rc;
Pushup(ch[x][]), Pushup(x);
}
int GetRank(int x,int val)
{
if(x==) return ;
if(val==key[x]) return siz[ch[x][]]+;
if(val<key[x]) return GetRank(ch[x][],val);
return siz[ch[x][]]+cnt[x]+GetRank(ch[x][],val);
}
int GetKth(int x,int k)
{
if(x==) return INF;
if(siz[ch[x][]]>=k) return GetKth(ch[x][],k);
if(siz[ch[x][]]+cnt[x]>=k) return key[x];
return GetKth(ch[x][],k-siz[ch[x][]]-cnt[x]);
}
void Insert(int &x,int val)
{
if(x==)
{
x=NewNode(val);
return;
}
if(val==key[x])
{
cnt[x]++;
Pushup(x);
return;
}
else if(val<key[x])
{
Insert(ch[x][],val);
if(dat[x] < dat[ch[x][]]) zig(x);
}
else
{
Insert(ch[x][],val);
if(dat[x] < dat[ch[x][]]) zag(x);
}
Pushup(x);
}
void Remove(int &x,int val)
{
if(x==) return;
if(val==key[x])
{
if(cnt[x]>)
{
cnt[x]--;
Pushup(x);
return;
}
if(ch[x][] || ch[x][])
{
if(ch[x][]== || dat[ch[x][]] > dat[ch[x][]]) zig(x), Remove(ch[x][],val);
else zag(x), Remove(ch[x][],val);
Pushup(x);
}
else x=;
return;
}
(val<key[x])?Remove(ch[x][],val):Remove(ch[x][],val);
Pushup(x);
}
int GetPre(int val)
{
int ans=; //a[1].val==-INF
int x=root;
while(x)
{
if(val==key[x])
{
if(ch[x][]>)
{
x=ch[x][];
while(ch[x][]>) x=ch[x][];
ans=x;
}
break;
}
if(key[x]<val && key[x]>key[ans]) ans=x;
x=(val<key[x])?ch[x][]:ch[x][];
}
return key[ans];
} int GetNxt(int val)
{
int ans=; //a[2].val==INF
int x=root;
while(x)
{
if(val==key[x])
{
if(ch[x][]>)
{
x=ch[x][];
while(ch[x][]>) x=ch[x][];
ans=x;
}
break;
}
if(key[x]>val && key[x]<key[ans]) ans=x;
x=(val<key[x])?ch[x][]:ch[x][];
}
return key[ans];
}
/******************************** Treap - ed ********************************/ int main()
{
int n;
cin>>n;
Build();
while(n--)
{
int opt,x;
scanf("%d%d",&opt,&x);
switch(opt)
{
case :
Insert(root,x);
break;
case :
Remove(root,x);
break;
case :
printf("%d\n",GetRank(root,x)-);
break;
case :
printf("%d\n",GetKth(root,x+));
break;
case :
printf("%d\n",GetPre(x));
break;
case :
printf("%d\n",GetNxt(x));
break;
}
}
}
注：本模板的 $zig(x)$ 和 $zag(x)$ 中 $x$，是旋转前处于父亲节点位置。
题解2：
Splay模板题。
Splay的原理以及实现参考：伸展树（Splay Tree）进阶 - 从原理到实现
AC代码（Splay）：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
const int maxn=1e5+; /******************************** splay - st ********************************/
#define Key_value ch[ch[root][1]][0]
int root,nodecnt;
int par[maxn],ch[maxn][];
int key[maxn],cnt[maxn],siz[maxn];
void NewNode(int &x,int p,int k)
{
x=++nodecnt;
par[x]=p;
ch[x][]=ch[x][]=;
key[x]=k;
cnt[x]=siz[x]=;
}
void Pushup(int x)
{
siz[x]=siz[ch[x][]]+siz[ch[x][]]+cnt[x];
}
void Rotate(int x,int type) //旋转，0为左旋zag，1为右旋zig
{
int y=par[x];
ch[y][!type]=ch[x][type]; par[ch[x][type]]=y;
if(par[y]) ch[par[y]][(ch[par[y]][]==y)]=x;
par[x]=par[y];
ch[x][type]=y; par[y]=x;
Pushup(y); Pushup(x);
}
void Splay(int x,int goal)
{
while(par[x]!=goal)
{
if(par[par[x]]==goal) Rotate(x,ch[par[x]][]==x); //左孩子zig，右孩子zag
else
{
int y=par[x];
int type=(ch[par[y]][]==y); //type=0，y是右孩子；type=1，y是左孩子
if(ch[y][type]==x)
{
Rotate(x,!type);
Rotate(x,type);
}
else
{
Rotate(y,type);
Rotate(x,type);
}
}
}
if(goal==) root=x;
}
int GetMin(int x)
{
while(ch[x][]) x=ch[x][];
return x;
}
int GetMax(int x)
{
while(ch[x][]) x=ch[x][];
return x;
}
void Init() //初始化，前后各加一个空节点
{
root=nodecnt=;
par[]=ch[][]=ch[][]=;
cnt[]=siz[]=;
key[]=;
NewNode(root,,-INF); //头部加入一个空位
NewNode(ch[root][],root,INF); //尾部加入一个空位
Pushup(ch[root][]);
Pushup(root);
} void Insert(int val)
{
int x=root;
while()
{
if(val==key[x])
{
cnt[x]++;
Pushup(x);
Splay(x,);
break;
}
int type=val>key[x];
if(ch[x][type]==)
{
NewNode(ch[x][type],x,val);
Pushup(x);
Splay(ch[x][type],);
break;
}
else x=ch[x][type];
}
}
void Delete(int val)
{
int x=root;
while(x)
{
if(val==key[x])
{
if(cnt[x]>)
{
cnt[x]--;
Pushup(x);
Splay(x,);
return;
}
if(ch[x][] && ch[x][])
{
Splay(GetMax(ch[x][]),);
Splay(GetMin(ch[x][]),root);
par[Key_value]=; Key_value=;
Pushup(ch[root][]); Pushup(root);
return;
}
int fa=par[x],type=(ch[fa][]==x);
if(ch[x][])
{
par[ch[x][]]=fa;
ch[fa][type]=ch[x][];
Pushup(fa);
Splay(ch[fa][type],);
return;
}
if(ch[x][])
{
par[ch[x][]]=fa;
ch[fa][type]=ch[x][];
Pushup(fa);
Splay(ch[fa][type],);
return;
}
ch[fa][type]=;
Pushup(fa);
Splay(fa,);
return;
}
if(val<key[x]) x=ch[x][];
else x=ch[x][];
}
}
int GetRank_pos;
int GetRank(int x,int val)
{
if(x==) return ;
if(val==key[x]) return siz[ch[GetRank_pos=x][]]+;
if(val<key[x]) return GetRank(ch[x][],val);
return siz[ch[x][]]+cnt[x]+GetRank(ch[x][],val);
}
int GetKth_pos;
int GetKth(int x,int k)
{
if(x==) return ;
if(siz[ch[x][]]>=k) return GetKth(ch[x][],k);
if(siz[ch[x][]]+cnt[x]>=k) return key[GetKth_pos=x];
return GetKth(ch[x][],k-siz[ch[x][]]-cnt[x]);
}
/******************************** splay - ed ********************************/ int main()
{
int n;
cin>>n;
Init();
while(n--)
{
int opt,x;
scanf("%d%d",&opt,&x);
switch(opt)
{
case :
Insert(x);
break;
case :
Delete(x);
break;
case :
printf("%d\n",GetRank(root,x)-);
Splay(GetRank_pos,);
break;
case :
printf("%d\n",GetKth(root,x+));
Splay(GetKth_pos,);
break;
case :
Insert(x);
printf("%d\n",key[GetMax(ch[root][])]);
Delete(x);
break;
case :
Insert(x);
printf("%d\n",key[GetMin(ch[root][])]);
Delete(x);
break;
}
}
}