对
by keven___ @ 2024-02-04 09:19:00
/bx/bx/bx/bx
by KingPowers @ 2024-02-04 11:22:14
@[egg_rat](/user/672534) 建议 @ 一下管理员/题解作者
by AAA404 @ 2024-02-05 12:07:58
@[Maxmilite](/user/274993)
by egg_rat @ 2024-02-05 13:37:58
为啥我写 treap $\text{get\_rank}$ 返回 $0$ WA 了，但返回 $1$ AC?
by _zuoqingyuan @ 2024-02-13 22:02:23
@[_zuoqingyuan](/user/731650) 因为最后减了一，排除负无穷节点
by egg_rat @ 2024-02-17 10:16:27
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N=1e5+10,inf=1e9+10;;
int tot,root,n,op,x;
struct node{
int l,r,cnt,size,dat,val;
}a[N];
int New(int val){
a[++tot].val=val;
a[tot].dat=rand();
a[tot].size=a[tot].cnt=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(){
root=New(-inf),a[root].r=New(inf);
update(root);
}
void zig(int &p){//右旋
int q=a[p].l;
a[p].l=a[q].r,a[q].r=p;
p=q,update(p),update(a[p].r);
}
void zag(int &p){//左旋
int q=a[p].r;
a[p].r=a[q].l,a[q].l=p;
p=q;update(p),update(a[p].l);
}
void insert(int &p,int val){// 插入
if(!p){
p=New(val);
return;
}else if(a[p].val==val){
a[p].cnt++;
update(p);
return;
}
else if(a[p].val>val){
insert(a[p].l,val);
if(a[p].dat<a[a[p].l].dat)zig(p);
}else if(a[p].val<val){
insert(a[p].r,val);
if(a[p].dat<a[a[p].r].dat)zag(p);
}
update(p);
}
void Delete(int &p,int val){// 删除
if(p==0)return;
if(a[p].val==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),Delete(a[p].r,val);
else
zag(p),Delete(a[p].l,val);
update(p);
}else p=0;
return;
}
a[p].val>val?Delete(a[p].l,val):Delete(a[p].r,val);
update(p);
}
int get_rank(int p,int val,int f){//查排名
if(!p)return 1;
else if(a[p].val==val)return a[a[p].l].size+1;
else if(val<a[p].val)return get_rank(a[p].l,val,1);
else return get_rank(a[p].r,val,2)+a[a[p].l].size+a[p].cnt;
}
int get_val(int p,int rank){// 查数
if(!p)return inf;
else if(rank<=a[a[p].l].size)return get_val(a[p].l,rank);
else if(rank<=a[a[p].l].size+a[p].cnt)return a[p].val;
else return get_val(a[p].r,rank-a[p].cnt-a[a[p].l].size);
}
int get_pre(int val){//前倾
int ans=-inf,p=root;
while(p){
if(a[p].val<val)ans=a[p].val,p=a[p].r;
else p=a[p].l;
}
return ans;
}
int get_next(int val){//后继
int ans=inf,p=root;
while(p){
if(a[p].val>val)ans=a[p].val,p=a[p].l;
else p=a[p].r;
}
return ans;
}
int main(){
build();
scanf("%d",&n);
while(n--){
scanf("%d %d",&op,&x);
if(op==1)insert(root,x);
if(op==2)Delete(root,x);
if(op==3)printf("%d\n",get_rank(root,x,0)-1);
if(op==4)printf("%d\n",get_val(root,x+1));
if(op==5)printf("%d\n",get_pre(x));
if(op==6)printf("%d\n",get_next(x));
}
return 0;
}
```
我代码这么写 AC 了，就是及排除负无穷，$\text{get\_rank()}$ 没查到返回 $1$。离谱
by _zuoqingyuan @ 2024-02-17 10:38:21