题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=3224
https://www.luogu.org/problemnew/show/P3369
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]
可能最近搞平衡二叉搜索树上瘾了？搞完替罪羊树再来搞搞无旋Treap。
关于无旋Treap：
我们已经知道了Treap是怎么写的：BZOJ 3224 - 普通平衡树 - [Treap][Splay]
我们知道，普通的Treap是要zigzag的，而无旋Treap顾名思义就是不需要zigzag。
无旋Treap最基本的（也是核心的）操作只有两种，一种 $Merge$，一种 $Split$。
$Split(x,k,a,b)$ 拆分操作：按照一个判定值 $k$ 将一个Treap $x$ 拆成两个Treap $a,b$（左树和右树），满足左树的所有值均小于等于 $k$，右树的所有值都大于 $k$。
$Merge(x,a,b)$ 合并操作：将两个Treap $a,b$ （满足 $a$ 中所有元素均小于 $b$ 中所有元素），合并成一个Treap $x$。合并的原则是节点的堆权值满足堆性质，所以是一种平衡树。
另外，与普通Treap不同的是，每个节点均只存一个元素；也就是说，若存在若干个相同元素，会有若干个节点，而非一个节点用 $cnt$ 去记录。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
const int maxn=1e5+; /******************************** FHQ Treap - st ********************************/
int root,nodecnt;
int ch[maxn][];
int key[maxn],dat[maxn];
int siz[maxn];
int NewNode(int val)
{
int x=++nodecnt;
key[x]=val, dat[x]=rand();
siz[x]=, ch[x][]=ch[x][]=;
return x;
}
void Pushup(int x) {
siz[x]=siz[ch[x][]]+siz[ch[x][]]+;
}
void Init()
{
root=nodecnt=;
key[]=dat[]=;
siz[]=, ch[][]=ch[][]=;
}
void Split(int x,int k,int &a,int &b)
{
if(x==)
{
a=b=;
return;
}
if(key[x]<=k) a=x, Split(ch[x][],k,ch[a][],b);
else b=x, Split(ch[x][],k,a,ch[b][]);
Pushup(x);
}
void Merge(int &x,int a,int b)
{
if(a== || b==)
{
x=a+b;
return;
}
if(dat[a]<dat[b]) x=a, Merge(ch[x][],ch[a][],b);
else x=b, Merge(ch[x][],a,ch[b][]);
Pushup(x);
} int GetRank(int val)
{
int a=,b=;
Split(root,val-,a,b);
int res=siz[a]+;
Merge(root,a,b);
return res;
}
int GetKth(int x,int k)
{
if(x==) return INF;
if(siz[ch[x][]]+==k) return key[x];
if(siz[ch[x][]]>=k) return GetKth(ch[x][],k);
else return GetKth(ch[x][],k-siz[ch[x][]]-);
}
void Insert(int val)
{
int a=,b=;
Split(root,val,a,b);
Merge(a,a,NewNode(val));
Merge(root,a,b);
}
void Remove(int val)
{
int a=,b=,c=;
Split(root,val,a,b);
Split(a,val-,a,c);
Merge(c,ch[c][],ch[c][]);
Merge(a,a,c);
Merge(root,a,b);
}
int GetPre(int val)
{
int a=,b=;
Split(root,val-,a,b);
int res=GetKth(a,siz[a]);
Merge(root,a,b);
return res;
}
int GetNxt(int val)
{
int a=,b=;
Split(root,val,a,b);
int res=GetKth(b,);
Merge(root,a,b);
return res;
}
/******************************** FHQ Treap - ed ********************************/ int main()
{
int n,opt,x;
scanf("%d",&n);
Init();
while(n--)
{
scanf("%d%d",&opt,&x);
if(opt==) Insert(x);
if(opt==) Remove(x);
if(opt==) printf("%d\n",GetRank(x));
if(opt==) printf("%d\n",GetKth(root,x));
if(opt==) printf("%d\n",GetPre(x));
if(opt==) printf("%d\n",GetNxt(x));
}
}
无旋Treap真的太好写了啊！！！QAQ又好写又好懂！！！比替罪羊树好多了QAQ！！！