删除的时候是用的把前驱和后继拉上来,然后孤立x点的方法
把前驱当作根,后继当作辅助点可以100pts AC(没有注释掉的erase
)
但是调换一下就44pts WA(注释掉的erase
)
私以为这两个应该是等价的啊……
Ball 聚捞解答
#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define MAXN 200001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template<typename T>
using namespace std;
namespace SlowIO{
Tp inline void rd(T &x){
x=0; bool f=1; char in=g();
while(!isdigit(in)) f&=(in!='-'),in=g();
while(isdigit(in)) x=(x<<3)+(x<<1)+(in^48),in=g();
x*=((f<<1)-1);
}
Tp inline void op(T x){
if(x<0) pc('-'),x=-x;
if(x>=10) op(x/10);
pc(x%10+48);
}
Tp inline void writeln(T x){ op(x),pc('\n'); }
Tp inline void writesp(T x){ op(x),pc(' '); }
Tp inline void writespf(T x){ pc(' '),op(x); }
}; using namespace SlowIO;
namespace SplayTree{
const int inf=2147483647;
int root,tot,siz[MAXN];
int fa[MAXN],son[MAXN][2];
int val[MAXN],cnt[MAXN];
inline void update(int x){ siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x]; }
inline bool chk(int x){ return x==son[fa[x]][1]; }
inline void rotate(int x){
ri ff=fa[x],ac=fa[ff]; //father & ancestor
register bool k=chk(x);
son[ac][chk(ff)]=x; //置换x和ff
fa[x]=ac;
son[ff][k]=son[x][k^1]; //给ff换上新son
fa[son[x][k^1]]=ff;
son[x][k^1]=ff; //把ff变成son
fa[ff]=x;
update(ff),update(x); //上传
} //旋转x
inline void splay(int x,int tar){
while(fa[x]!=tar){
ri ff=fa[x],ac=fa[ff];
if(ac!=tar) rotate(chk(ff)^chk(x)?x:ff);
rotate(x);
} if(!tar) root=x;
} //伸展为tar的son
inline void find(int x){
ri cur=root;
if(!cur) return;
while(son[cur][val[cur]<x]&&val[cur]!=x)
cur=son[cur][val[cur]<x];
splay(cur,0);
} //把最接近x的值旋转到根
inline void insert(int x){
ri cur=root,ff=0;
while(cur&&val[cur]!=x)
ff=cur,cur=son[cur][val[cur]<x];
if(cur) ++cnt[cur];
else{
cur=++tot;
if(ff) son[ff][val[ff]<x]=cur;
val[cur]=x,fa[cur]=ff;
siz[cur]=cnt[cur]=1;
} splay(cur,0);
} //插入x
inline int fixes(int x,bool f){
find(x); ri cur=root;
if(val[cur]<x&&!f) return cur;
if(val[cur]>x&&f) return cur;
cur=son[cur][f],f^=1;
while(son[cur][f]) cur=son[cur][f];
return cur;
} //找前后缀 0前缀 1后缀
inline int getkth(int k){
ri cur=root;
while(cur){
if(son[cur][0]&&k<=siz[son[cur][0]]) cur=son[cur][0];
else{
k-=siz[son[cur][0]]+cnt[cur];
if(k<=0){
splay(cur,0);
return val[cur];
} cur=son[cur][1];
}
}
} //找第k大数
inline void debug(int x){
if(!x) return;
debug(son[x][0]);
writesp(siz[x]);
debug(son[x][1]);
}
inline int getrnk(int x){ find(x); return siz[son[root][0]]; }
// inline void erase(int x){
// ri rig=fixes(x,1),lef=fixes(x,0);
// splay(rig,0),splay(lef,rig);
// //此时x位于前驱lef的右儿子且无子树
// x=son[lef][1]; if(cnt[x]>1) --cnt[x],splay(x,0);
// else son[lef][1]=0;
// }
inline void erase(int x){
ri rig=fixes(x,1),lef=fixes(x,0);
splay(lef,0),splay(rig,lef);
x=son[rig][0]; if(cnt[x]>1) --cnt[x],splay(x,0);
else son[rig][0]=0;
}
}; using namespace SplayTree;
int main()
{
ri n,opt,x; insert(inf),insert(-inf);
rd(n); while(n--){
rd(opt),rd(x);
if(opt==1) insert(x);
if(opt==2) erase(x);
if(opt==3) writeln(getrnk(x));
if(opt==4) writeln(getkth(x+1));
if(opt==5) writeln(val[fixes(x,0)]);
if(opt==6) writeln(val[fixes(x,1)]);
}
return 0;
}