没想到学了那么久的文化课后现在连splay都不会写了,求大佬康康
还有关于删除操作
开始是这么写
inline void erase(int x) {
int pre=next(x,0),suf=next(x,1);
splay(suf,0); splay(pre,suf);
int now=son[pre][1];
if(cnt[now]<=1) son[pre][1]=0;
else cnt[now]--;
}
如果改成这么写
inline void erase(int x) {
int pre=next(x,0),suf=next(x,1);
splay(pre,0); splay(suf,pre);
int now=son[suf][0];
if(cnt[now]<=1) son[suf][0]=0;
else cnt[now]--;
}
还能多A几个点???
求教为什么/kel
#include <cstdio>
#include <algorithm>
#include <cstring>
const int mod=1e9+7;
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define pb push_back
const int maxn=1e5+6;
const int inf=0x3f3f3f3f;
template<class T>inline void read(T &x) {
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s&15);s=getchar();}
x*=f;
}
inline int min(int a,int b) { return a<b?a:b; }
inline int max(int a,int b) { return a>b?a:b; }
inline void swap(int &x,int &y) { x^=y^=x^=y; }
int val[maxn],son[maxn][2],fa[maxn],root,f,ff,num,cnt[maxn],siz[maxn];
inline void pushup(int x) {
siz[x]=cnt[x]+siz[son[x][0]]+siz[son[x][1]];
}
inline int check(int x) { return (son[fa[x]][1]==x); }
inline void rotate(int x) {
int chk=check(x); f=fa[x],ff=fa[f];
son[ff][check(f)]=x; fa[x]=ff;
son[f][chk]=son[x][chk^1]; fa[son[x][chk^1]]=f;
son[x][chk^1]=f; fa[f]=x;
pushup(f); pushup(x);
}
inline void splay(int x,int goal) {
while(fa[x]!=goal) {
f=fa[x]; ff=fa[f];
if(ff!=goal) (check(x)^check(f))?rotate(x):rotate(f);
rotate(x);
}
if(!goal) root=x;
}
inline void insert(int x) {
int now=root;
while(now&&val[now]!=x) f=now,now=son[now][x>val[now]];
if(now) cnt[now]++;
else {
now=++num;
son[f][x>val[f]]=now; fa[now]=f; son[now][0]=0; son[now][1]=0;
val[now]=x; cnt[now]=1; siz[now]=1;
}
splay(now,0);
}
inline void find(int x) {
int now=root;
while(son[now][x>val[now]]&&val[now]!=x) now=son[now][x>val[now]];
splay(now,0);
}
inline int next(int x,int tag) {//tag=0:前驱 tag=1:后继
find(x);
if(val[root]<x&&(!tag)) return root;
if(val[root]>x&&tag) return root;
int now=root;
now=son[now][tag];
while(son[now][tag^1]) now=son[now][tag^1];
return now;
}
inline int rank(int x) {
find(x);
return siz[son[root][0]];
}
inline int kth(int x) {
int now=root;
while(1) {
if(x>(siz[son[now][0]]+cnt[now])) x-=(siz[son[now][0]]+cnt[now]),now=son[now][1];
else if(son[now][0]&&x<=siz[son[now][0]]) now=son[now][0];
else return now;
}
}
inline void erase(int x) {
int pre=next(x,0),suf=next(x,1);
splay(suf,0); splay(pre,suf);
int now=son[pre][1];
if(cnt[now]<=1) son[pre][1]=0;
else cnt[now]--;
}
int n,opt,x;
int main() {
read(n);
insert(-inf); insert(inf);
rep(i,1,n) {
read(opt); read(x);
if(opt==1) insert(x);
if(opt==2) erase(x);
if(opt==3) printf("%d\n",rank(x));
if(opt==4) printf("%d\n",val[kth(x+1)]);
if(opt==5) printf("%d\n",val[next(x,0)]);
if(opt==6) printf("%d\n",val[next(x,1)]);
}
}