题目描述：
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入数值x。
- 删除数值x(若有多个相同的数，应只删除一个)。
- 查询数值x的排名(若有多个相同的数，应输出最小的排名)。
- 查询排名为x的数值。
- 求数值x的前驱(前驱定义为小于x的最大的数)。
- 求数值x的后继(后继定义为大于x的最小的数)。
输入格式
第一行为n，表示操作的个数。
接下来n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)。
输出格式
对于操作3,4,5,6每行输出一个数，表示对应答案。
数据范围
n≤100000n≤100000,所有数均在−107−107到107107内。
输入样例：
8 1 10 1 20 1 30 3 20 4 2 2 10 5 25 6 -1
输出样例：
2 20 20 20
这道题是最基本的BST+Treap板子题，直接套板子然后考虑细节就行，
关于算法可以参考这两篇博客
BST
Treap
AC代码：
/*
MMM
MMMMMMM:
~MM MMM
7M+ MM
MM
MMMMMM, MM MM ,,:+MMM:
MMM MMM MM~ MM ~MMMMMMMMMMMMMMMMMMMMMMM$
ZM$ MMM MM MMMMMMMMMN MMM MMM$
MM MM8 MM OMMMMMO MM MM~
,MM MM ,MMMMM MM MMMMMMZ ,MM MMM
MM? MMDMMMMM+ , MM MM, ~MD , MM
MM8 :MMMO IMMM, MMÁÁÁÁ MM MM MMM ,MMO MM
MMM MMMMM MMMMMMM MM M8 MM MMM MM NM
MMMMMM MM ~MM MM7 MM MM7 DM
7MMM MM ÁÁÁÁ MM MMMMMM MM? MM
MMM M MM MM MMD :MM
MMM MMM IMM NMMM IMM
NMM 7MMMMMM MMMMMMMMM
MMM
MM MMM
MM DMM? MMM:
7MM MMMMMMMMMM MMMM
MM MMM MMMN MMMMMM7
MM MM MMD MMMMM
DM~ MM MM MM
NM MM MM MM=
MM MM NM MM
NM +MM MM NM MM
OM? MMM 8MM ,MM ZMZ
MM MMMM :MMM +? MMM MM
MM MMMMMMM: MM =MM +MM
MM: MMM MMM MM
MM MMMMMMMMMMMMM? MM
MM+ ?MMMMM$ MM7
MM MM
MM MM
=MM ZMM
MMM MMMM
~MMMMM MMMMMM
MM ?MMMM 8MMMM MM
MM MMMMMMN, NMMMMM ,MM
ZMM =MMMMMMMMMMMMMM DMM
,MMMMOMM8 MM7MMMM
MMM? MMM, MMMM ,MMM +MMM MMM
MM MMMM 7MMM MM MM ?MMM 8MMM8 M
:MMM NMM~ MM MM MMM MMMM
MO MM MM MM DMI ?ND
~M,ZMNIM MM 8MM :M M$ MM
MM MM MM MOM8MMM
~ MM MM D
OM? ~MM
MMMM MM MM
M MM M= MM =MM
MM M~MMMMNMMN MN
M M,MM+M?MM MM
MNOMMM ,,NDMM MM
MMM MM
MM MM
+M$ MM
MM MM
MM MM
MMMMMMMMMMMMMMMMMMMMMMMMMMNNNNNNDDZZZZIIIIIIIZZZDNMMMMM
, :~IZ8DNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMN
NM MZ MM M
NM M7 MM7M
NM M+ MMDM
DM M= MMMM
DM M MMMM ZM=
DMMMMMMMMMMMMN MMMMMMMMMMMMM=
MM MM MM MM
~MMMMMMMMMMMM8 +MMMMMMMMMMMM
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;
const int N = 100010;
struct Treap
{
int l, r;
int val, dat;
int cnt, size;
} a[N];
int tot, root, n;
int New(int val)
{
a[++tot].val=val;
a[tot].dat=rand();
a[tot].cnt=a[tot].size=1;
return tot;
}
void Update(int p)
{
a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;
}
void Build()
{
New(-INF),New(INF);
root=1,a[1].r=2;
Update(root);
}
int GetRankByVal(int p, int val)
{
if (p==0)
return 0;
if (val==a[p].val)
return a[a[p].l].size + 1;
if (val<a[p].val)
return GetRankByVal(a[p].l,val);
return GetRankByVal(a[p].r,val)+a[a[p].l].size+a[p].cnt;
}
int GetValByRank(int p, int rank)
{
if(p==0)
return INF;
if(a[a[p].l].size>=rank)
return GetValByRank(a[p].l,rank);
if (a[a[p].l].size + a[p].cnt>=rank)
return a[p].val;
return GetValByRank(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}
void zig(int &p)
{
int q=a[p].l;
a[p].l=a[q].r;
a[q].r=p;
p=q;
Update(a[p].r);
Update(p);
}
void zag(int &p)
{
int q=a[p].r;
a[p].r=a[q].l;
a[q].l=p;
p=q;
Update(a[p].l);
Update(p);
}
void Insert(int &p, int val)
{
if(p==0)
{
p=New(val);
return ;
}
if(val==a[p].val)
{
a[p].cnt++;
Update(p);
return ;
}
if(val<a[p].val)
{
Insert(a[p].l,val);
if (a[p].dat<a[a[p].l].dat)
zig(p);
}
else
{
Insert(a[p].r,val);
if (a[p].dat<a[a[p].r].dat)
zag(p);
}
Update(p);
}
int Getpre(int val)
{
int ans=1;
int p=root;
while(p)
{
if(val==a[p].val)
{
if(a[p].l>0)
{
p=a[p].l;
while(a[p].r>0)
p=a[p].r;
ans=p;
}
break;
}
if(a[p].val<val&&a[p].val>a[ans].val)
ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
return a[ans].val;
}
int Getnext(int val)
{
int ans=2;
int p=root;
while(p)
{
if(val==a[p].val)
{
if(a[p].r>0)
{
p=a[p].r;
while(a[p].l>0)
p=a[p].l;
ans=p;
}
break;
}
if(a[p].val>val&&a[p].val<a[ans].val)
ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
return a[ans].val;
}
void Remove(int &p, int val)
{
if(p==0)
return ;
if(val==a[p].val)
{
if(a[p].cnt>1)
{
a[p].cnt--;
Update(p);
return;
}
if (a[p].l||a[p].r)
{
if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat)
{
zig(p);
Remove(a[p].r,val);
}
else
{
zag(p);
Remove(a[p].l,val);
}
Update(p);
}
else p = 0;
return ;
}
val<a[p].val?Remove(a[p].l,val):Remove(a[p].r,val);
Update(p);
}
int main()
{
Build();
cin >> n;
while(n--)
{
int opt,x;
cin>>opt>>x;
switch (opt)
{
case 1:
Insert(root,x);
break;
case 2:
Remove(root,x);
break;
case 3:
cout<<GetRankByVal(root,x)-1<<endl;
break;
case 4:
cout<<GetValByRank(root,x+1)<<endl;
break;
case 5:
cout<<Getpre(x)<<endl;
break;
case 6:
cout<<Getnext(x)<<endl;
break;
}
}
return 0;
}
标签：return,val,Treap,BST,3224,Update,MMM,MM,int From： https://blog.51cto.com/u_15952369/6035597