贴个代码
by Erusel @ 2019-02-21 13:43:29
@[Robinzh](/space/show?uid=53807) @[LZDQ](/space/show?uid=116116)
by Erusel @ 2019-02-21 13:43:39
@[Robinzh](/space/show?uid=53807)
看不见吗
这里有个新的
https://www.luogu.org/recordnew/show/16535800
```cpp
#include<cstdio>
#include<cstdlib>
#include<ctime>
inline int maxx(int a,int b){
if(a>b) return a;
return b;
}
inline int minn(int a,int b){
if(a<b) return a;
return b;
}
const int MAXN=1e5+5,INF=0x7fffffff;
int n,rt;
int cnt;
int val[MAXN],siz[MAXN],chl[MAXN][2],key[MAXN],rpt[MAXN];
int x;
void Print(const int u){
if(!u) return ;
printf("%d lc %d rc %d val %d key %d\n",u,chl[u][0],chl[u][1],val[u],key[u]);
Print(chl[u][0]);
Print(chl[u][1]);
return ;
}
inline void zg(int &u,const bool d){
//d=1 zig
//d=0 zag
const int k=chl[u][!d];
chl[u][!d]=chl[k][d];
chl[k][d]=u;
siz[k]=siz[u];
siz[u]=siz[chl[u][0]]+siz[chl[u][1]]+rpt[u];
u=k;
}
void Insrt(int &u){
// printf("Insert %d\n",u);
if(!u){
u=++cnt;
val[u]=x;
key[u]=rand();
siz[u]=rpt[u]=1;
chl[u][0]=chl[u][1]=0;
return ;
}
++siz[u];
if(val[u]==x) return ++rpt[u],void();
const bool d=x>val[u];
Insrt(chl[u][d]);
// Print(chl[u][d]);
if(key[chl[u][d]]<key[u]) zg(u,!d);
return ;
}
void Del(int &u){
--siz[u];
if(val[u]!=x)
return Del(chl[u][x>val[u]]);
if(!--rpt[u]){
if(!chl[u][0]||!chl[u][1])
u=chl[u][0]+chl[u][1];
else{
const bool d=key[chl[u][0]]>key[chl[u][1]];
zg(u,!d);
Del(u);
}
}
return ;
}
int QueryRk(){
int p=rt,res=0;
while(p){
if(x==val[p]) return res+siz[chl[p][0]]+1;
if(x<val[p]) p=chl[p][0];
else res+=siz[chl[p][0]]+rpt[p],p=chl[p][1];
}
return res;
}
int QueryKth(const int u,const int k){
const int s=siz[chl[u][0]];
if(s+1==k) return val[u];
if(s>=k) return QueryKth(chl[u][0],k);
return QueryKth(chl[u][1],k-s);
}
int Pre(const int u){
if(!u) return -INF;
if(val[u]<x) return maxx(val[u],Pre(chl[u][1]));
return Pre(chl[u][0]);
}
int Suf(const int u){
// printf("Query Suf %d val %d\n",u,val[u]);
// printf("lc %d rc %d\n",chl[u][0],chl[u][1]);
if(!u) return INF;
if(val[u]>x) return minn(val[u],Suf(chl[u][0]));
return Suf(chl[u][1]);
}
int main(){
// freopen("2971-2.in","r",stdin);
srand(time(0));
scanf("%d",&n);
while(n--){
int opt;
scanf("%d%d",&opt,&x);
if(opt==0) return fclose(stdin),0;
if(opt==1) Insrt(rt);
else if(opt==2) Del(rt);
else if(opt==3) printf("%d\n",QueryRk());
else if(opt==4) printf("%d\n",QueryKth(rt,x));
else if(opt==5) printf("%d\n",Pre(rt));
else printf("%d\n",Suf(rt));
// printf("%d %d\n",opt,x),Print(rt),puts("");
}
// fclose(stdin);
return 0;
}
```
by LZDQ @ 2019-02-21 13:50:04
你fclose(stdin)没删
by Erusel @ 2019-02-21 13:54:41
@[LZDQ](/space/show?uid=116116)
by Erusel @ 2019-02-21 13:54:54
opt==0没关系
by LZDQ @ 2019-02-21 14:02:28
@[Robinzh](/space/show?uid=53807)
by LZDQ @ 2019-02-21 14:02:41
@[LZDQ](/space/show?uid=116116) 好吧
by Erusel @ 2019-02-21 14:09:50