@[I_love_xzo](/user/505805) 首先 siz 的 Update 要加 1（？
by tribool4_in @ 2022-03-28 13:32:46
@[wangwls](/user/341650) 噗似乎雀食是这样
我先试试
by Masna_Kimoyo @ 2022-03-28 13:33:44
@[wangwls](/user/341650) 还是不行qwq
by Masna_Kimoyo @ 2022-03-28 13:39:54
@[I_love_xzo](/user/505805)
```cpp
#include<bits/stdc++.h>
#define printlf(x) print(x),putchar('\n')
#define printsp(x) print(x),putchar(' ')
using namespace std;
inline int read(){
int x=0;
bool w=0;
char c=getchar();
while(!isdigit(c)) w|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline void print(int x){
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar('0'+x%10);
}
namespace FHQ_Treap{
const int N=1e5+5;
struct node{
int val,rd,siz;
int s[2];
}tree[N];
int p1,p2,p3,root,num;
inline void Update(int x){
tree[x].siz=tree[tree[x].s[1]].siz+tree[tree[x].s[0]].siz+1;
}
inline void split(int p,int val,int &x,int &y){
if(!p) {
x=y=0;
return ;
}
if(tree[p].val<=val) x=p,split(tree[p].s[1],val,tree[p].s[1],y);
else y=p,split(tree[p].s[0],val,x,tree[p].s[0]);
Update(p);
}
inline int merge(int x,int y){
if(x==0 || y==0) return x+y;
if(tree[x].rd<tree[y].rd){
tree[x].s[1]=merge(tree[x].s[1],y);
Update(x);
return x;
}
tree[y].s[0]=merge(x,tree[y].s[0]);
Update(y);
return y;
}
inline int Newnode(int x){
tree[++num].siz=1,tree[num].val=x,tree[num].rd=rand();
return num;
}
inline void Insert(int x){
split(root,x,p1,p2);
root=merge(merge(p1,Newnode(x)),p2);
}
inline void Delete(int x){
split(root,x,p1,p3),split(root,x-1,p1,p2);
p2=merge(tree[p2].s[0],tree[p2].s[1]);
root=merge(merge(p1,p2),p3);
}
inline int Rank(int x){
split(root,x-1,p1,p2);
int ans = tree[p1].siz+1;
root=merge(p1,p2);
return ans;
}
inline int Find(int p,int x){
while(1){
if(x<=tree[tree[p].s[0]].siz) {
p=tree[p].s[0];
continue;
}
if(x==tree[tree[p].s[0]].siz+1) return tree[p].val;
x-=tree[tree[p].s[0]].siz+1,p=tree[p].s[1];
}
}
}
signed main(){
srand(time(NULL));
using namespace FHQ_Treap;
int n=read();
while(n--){
int op=read();
if(op==1) Insert(read());
if(op==2) Delete(read());
if(op==3) printlf(Rank(read()));
if(op==4) printlf(Find(root,read()));
if(op==5) printlf(Find(root, Rank(read()) - 1));
if(op==6) printlf(Find(root, Rank(read() + 1)));
}
return 0;
}
```
改了下 Rank，以及前驱后继。
by tribool4_in @ 2022-03-28 13:58:38
@[_kevin320_](/user/199459)
by tribool4_in @ 2022-03-28 13:58:52