题意
维护一些数，其中需要提供以下操作：
- 1.插入\(x\)
- 2.删除\(x\)(若有多个相同的数，只删除一个)
- 3.查询\(x\)的排名(排名定义为比当前数小的数的个数\(+1\))
- 4.查询排名为\(x\)的数
- 5.求最大的小于\(x\)数
- 6.求最小的大于\(x\)数
\(n \leq 100000\)
思路
这是一道\(treap\)模板
\(Treap=tree+heap\)
下图是一棵二叉排序树
性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
但是有一个问题，如果被卡之后很有可能变成一棵“链”搜索树。然后堆就现身了，可以随机另外附权值，在二叉排序树基础上，它还需要满足随机权值是小根堆，这时候就需要一个旋转操作。
这样子就可以让一些链重新压扁成树，而这些旋转操作，只会影响到三个点
void cal(int x){
size[x]=size[s[x][0]]+size[s[x][1]]+1;
}
void r(int &k,int p){
int t=s[k][p];
s[k][p]=s[t][!p],s[t][!p]=k;
cal(k),cal(t);
k=t;
}
然后就可以开始进行操作了，操作就是在普通二叉树上加上旋转操作
- 1.插入：找到这个点的位置，给每个点随机一个优先级，然后如果它的优先级要小于父节点，我们就把它旋转上去。
void ins(int &k,int x){
if (!k){
k=++cnt,w[k]=x,pos[k]=rand()*rand()%19620817,size[k]=1;
return;
}
size[k]++;
if (x<=w[k]){
ins(s[k][0],x);
if(pos[s[k][0]]<pos[k]) r(k,0);
}else{
ins(s[k][1],x);
if (pos[s[k][1]]<pos[k]) r(k,1);
}
}
- 2.删除：有点像堆的删除，先看看有没有。有的话找到这个点，将这个点优先级小的子节点旋转上来，一直将其旋到叶子，然后删除。
bool f(int k,int x){
if (w[k]==x) return 1;
if (!k) return 0;
if (w[k]>x) return f(s[k][0],x);
return f(s[k][1],x);
}
void del(int &k,int x){
if (x>w[k]) del(s[k][1],x);
else if (x<w[k]) del(s[k][0],x);
else{
if (s[k][0]*s[k][1]==0) {
k=s[k][0]+s[k][1];
return;
}
if (pos[s[k][0]]<pos[s[k][1]]) {r(k,0);del(s[k][1],x);}
else {r(k,1);del(s[k][0],x);}
}
cal(k);
}
- 3.查找\(x\)的排名:只要看左右子树的大小就可以了，但是要注意一点：因为查询的是最小的排名，所以当我们查到\(x\)的时候，不能直接返回，而要递归下去，直到到达叶节点为止
int find(int k,int x){
if (!k) return 1;
if (x<=w[k]) return find(s[k][0],x);
return size[s[k][0]]+1+find(s[k][1],x);
}
- 4.查询排名为\(x\)的数：直接左右子树判一判查下去
int find2(int k,int x){
if (x-1==size[s[k][0]]) return w[k];
if (x>size[s[k][0]]) return find2(s[k][1],x-size[s[k][0]]-1);
else return find2(s[k][0],x);
}
- 5.求最大的小于\(x\)数
- 6.求最小的大于\(x\)数
两个操作非常相似,如果找到了小于\(x\)的，则还要看一看左子树还有没比\(x\)小的，否则就去右子树。
int pre(int k,int x){
if (!k) return -INF;
if (w[k]<x) return max(pre(s[k][1],x),w[k]);
return pre(s[k][0],x);
}
int Next(int k,int x){
if (!k) return INF;
if (w[k]>x) return min(w[k],Next(s[k][0],x));
return Next(s[k][1],x);
}
完整版把上面所有的合在一起就好了