所以为什么不打权值线段树呢？

权值线段树真好吃.

参考

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson root<<1
#define rson root<<1|1
using namespace std;
struct node {
    int l,r,sum;
} tr[800080];

struct opt {
    int kd,x;
} op[100010];
int cnt,a[100010];
void push_up(int root) {
    tr[root].sum=tr[lson].sum+tr[rson].sum;
}
void build(int root,int l,int r) {
    if(l==r) {
        tr[root].l=l;
        tr[root].r=r;
        tr[root].sum=0;
        return ;
    }
    tr[root].l=l;
    tr[root].r=r;
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    push_up(root);
}
void update(int root,int pos,int val) {
    if(tr[root].l==pos&&tr[root].r==pos) {
        tr[root].sum+=val;
        return ;
    }
    int mid=(tr[root].l+tr[root].r)>>1;
    if(mid>=pos) {
        update(lson,pos,val);
    } else {
        update(rson,pos,val);
    }
    push_up(root);
}
int query(int root,int l,int r) {
    if(l>r) {
        return 0;
    }
    if(tr[root].l==l&&tr[root].r==r) {
        return tr[root].sum;
    }
    int mid=(tr[root].l+tr[root].r)>>1;
    if(mid<l) {
        return query(rson,l,r);
    } else {
        if(r<=mid) {
            return query(lson,l,r);
        } else {
            return query(lson,l,mid)+query(rson,mid+1,r);
        }
    }
}
int kth(int root,int k) {
    if(tr[root].l==tr[root].r) {
        return tr[root].l;
    }
    if(tr[lson].sum>=k) {
        return kth(lson,k);
    } else {
        return kth(rson,k-tr[lson].sum);
    }
}
int Rank(int x) {
    int pos=lower_bound(a+1,a+cnt+1,x)-a;
    return query(1,1,pos-1)+1;
}
int pre(int root,int pos) {
    int l=1,r=pos-1,mid;
    while(l<r) {
        mid=(l+r)>>1;
        if(query(1,mid+1,r)) {
            l=mid+1;
        } else {
            r=mid;
        }
    }
    return r;
}
int next(int root,int pos) {
    int l=pos+1,r=cnt,mid;
    while(l<r) {
        mid=(l+r)>>1;
        if(query(1,l,mid)) {
            r=mid;
        } else {
            l=mid+1;
        }
    }
    return l;
}
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d%d",&op[i].kd,&op[i].x);
        if(op[i].kd!=2&&op[i].kd!=4) {
            a[++cnt]=op[i].x;
        }
    }
    sort(a+1,a+cnt+1);
    cnt=unique(a+1,a+cnt+1)-a-1;
    build(1,1,cnt);
    for(int i=1; i<=n; i++) {
        if(op[i].kd==1) {
            int pos=lower_bound(a+1,a+cnt+1,op[i].x)-a;
            update(1,pos,1);
        }
        if(op[i].kd==2) {
            int pos=lower_bound(a+1,a+cnt+1,op[i].x)-a;
            update(1,pos,-1);
        }
        if(op[i].kd==3) {
            printf("%d\n",Rank(op[i].x));
        }
        if(op[i].kd==4) {
            int pos=kth(1,op[i].x);
            printf("%d\n",a[pos]);
        }
        if(op[i].kd==5) {
            int pos=lower_bound(a+1,a+cnt+1,op[i].x)-a;
            printf("%d\n",a[pre(1,pos)]);
        }
        if(op[i].kd==6) {
            int pos=lower_bound(a+1,a+cnt+1,op[i].x)-a;
            printf("%d\n",a[next(1,pos)]);
        }
    }
}