rt,大佬帮忙改一下,谢谢。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define sc scanf
#define pr printf
#define inf 0x3f3f3f3f
inline int read(){int s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-') w=-1;c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return s*w;}
const int N = 1e5 + 10;
int root,idx;
struct node{
int l,r;
int key;
int val;
int size;
int cnt;
}tr[N];
inline int get(int key){
return tr[++idx].key = key , tr[idx].val = rand() ,tr[idx].size = tr[idx].cnt = 1 , idx;
}
inline void pushup(int u){
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}
inline void rturn(int &rt){
int q = tr[rt].l;
tr[rt].l = tr[q].r;
tr[q].r = rt;
rt = q;
pushup(tr[rt].r);
pushup(rt);
}
inline void lturn(int &rt){
int q = tr[rt].r;
tr[rt].r = tr[q].l;
tr[q].l = rt;
rt = q;
pushup(tr[rt].l);
pushup(rt);
}
inline void build(){
get(-inf);
get(inf);
root = 1;
tr[root].r = 2;
pushup(root);
if(tr[1].val < tr[2].val) lturn(root);
}
inline void insert(int &rt,int key){
if(!rt){
rt = get(key);
return;
}
if(tr[rt].key == key) tr[rt].cnt++;
if(tr[rt].key > key) {insert(tr[rt].l , key) ; if(tr[tr[rt].l].val > tr[rt].val) rturn(rt);}
if(tr[rt].key < key) {insert(tr[rt].r , key) ; if(tr[tr[rt].r].val > tr[rt].val) lturn(rt);}
pushup(rt);
}
inline void del(int &rt,int key){
if(!rt) return;
if(tr[rt].key == key){
if(tr[rt].cnt > 1) tr[rt].cnt --;
else {
if(tr[rt].l || tr[rt].r){
if(!tr[rt].r || tr[tr[rt].l].val > tr[tr[rt].r].val) rturn(rt) ,del(tr[rt].r , key);
else lturn(rt) , del(tr[rt].l , key);
}
else rt = 0;
}
}
else if(tr[rt].key > key) del(tr[rt].l , key);
else del(tr[rt].r , key);
pushup(rt);
}
inline int get_rank_by_key(int rt,int key){
if(!rt) return 0;
if(tr[rt].key == key) return tr[tr[rt].l].size + 1;
else if(tr[rt].key > key) get_rank_by_key(tr[rt].l,key);
else return tr[tr[rt].l].size + tr[rt].cnt + get_rank_by_key(tr[rt].r,key);
}
inline int get_key_by_rank(int rt,int rank){
if(!rt) return 0;
if(tr[tr[rt].l].size >= rank) return get_key_by_rank(tr[rt].l,rank);
else if(tr[tr[rt].l].size + tr[rt].cnt >= rank) return tr[rt].key;
else return get_key_by_rank(tr[rt].r,rank-tr[tr[rt].l].size-tr[rt].cnt);
}
inline int get_pre(int rt,int key){
if(!rt) return -inf;
if(tr[rt].key >= key) return get_pre(tr[rt].l,key);
else return max(tr[rt].key , get_pre(tr[rt].r , key));
}
inline int get_next(int rt,int key){
if(!rt) return inf;
if(tr[rt].key <= key) return get_next(tr[rt].r,key);
else return min(tr[rt].key , get_next(tr[rt].l , key));
}
signed main(){
srand(time(0));
build();
int Q = read();
while(Q--){
int op = read() , x = read();
if(op == 1) insert(root, x);
if(op == 2) del(root , x);
if(op == 3) pr("%lld\n",get_rank_by_key(root ,x) - 1);
if(op == 4) pr("%lld\n",get_key_by_rank(root ,x + 1));
if(op == 5) pr("%lld\n",get_pre(root , x));
if(op == 6) pr("%lld\n",get_next(root , x));
}
return 0;
}