```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define lc t[x].l
#define rc t[x].r
const int mod=5302121,pri=832211;
const int N=1e5+5;
int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*f;
}
inline int rand()
{
static int set=15;
return set=(long long)(set*pri)%mod;
}
struct node{
int l,r,v,w,size,rnd;
}t[N];
int cnt=0,root;
inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;}
inline void rturn(int &x){
int c=lc;lc=t[c].r;t[c].r=x;
t[c].size=t[x].size;update(x);x=c;
}
inline void lturn(int &x){
int c=rc;rc=t[c].l;t[c].l=x;
t[c].size=t[x].size;update(x);x=c;
}
void ins(int &x,int v){
if(x==0){
cnt++;x=cnt;
t[cnt].l=t[cnt].r=0;t[cnt].size=t[cnt].w=1;
t[cnt].v=v;t[cnt].rnd=rand();
return;
}
t[x].size++;
if(t[x].v==v) {t[x].w++;return;}
if(v<t[x].v){
ins(lc,v);
if(t[lc].rnd<t[x].rnd) rturn(x);
}else{
ins(rc,v);
if(t[rc].rnd<t[x].rnd) lturn(x);
}
}
void del(int &x,int v){
if(x==0) return;
if(t[x].v==v){
if(t[x].w>1){t[x].w--,t[x].size--;return;}
if(lc*rc==0) x=lc+rc;
else if(t[lc].rnd<t[rc].rnd) rturn(x),del(x,v);
else lturn(x),del(x,v);
}else{
t[x].size--;
if(v<t[x].v) del(lc,v);
else del(rc,v);
}
}
int rnk(int x,int v){
if(t[x].v==v) return t[lc].size+1;
if(v<t[x].v) return rnk(lc,v);
else return t[lc].size+t[x].w+rnk(rc,v);
}
int kth(int x,int k){
if(x==0) return 0;
if(k<=t[lc].size) return kth(lc,k);
else if(k>t[lc].size+t[x].w) return kth(rc,k-t[lc].size-t[x].w);
else return t[x].v;
}
int ans;
void pre(int x,int v){
if(x==0) return;
if(v>t[x].v) ans=x,pre(rc,v);
else pre(lc,v);
}
void suf(int x,int v){
if(x==0) return;
if(v<t[x].v) ans=x,suf(lc,v);
else suf(rc,v);
}
int main(int argc, const char * argv[]) {
freopen("s.in","r",stdin);
srand(222);
int n=read(),op,x;
while(n--){
if(n == 1)
n=1;
op=read();x=read();
switch(op){
case 1:ins(root,x);break;
case 2:del(root,x);break;
case 3:printf("%d\n",rnk(root,x));break;
case 4:printf("%d\n",kth(root,x));break;
case 5:ans=0;pre(root,x);printf("%d\n",t[ans].v);break;
case 6:ans=0;suf(root,x);printf("%d\n",t[ans].v);break;
}
}
return 0;
}
```
这个是dalao的满分
by Eagle_WYX @ 2018-07-12 10:02:04
权值线段树了解一下。
by a13518354766 @ 2018-07-12 10:05:55
已过！！！（补觉，逃！
by Eagle_WYX @ 2018-07-12 10:54:57
# 20小时？？？骗人的吧
by 洛倾然 @ 2018-07-12 22:02:58
过了就不能讲讲怎么过的吗...
遇到一样的问题了
by ix35 @ 2019-02-04 12:05:55