Problem 普通平衡树
Solution
本题是裸的二叉平衡树。有很多种方法可以实现。这里打的是替罪羊树模板。
此题极其恶心。
前驱后继模块需要利用到rank模块来换一种思路求。
很多细节的地方容易炸。我拿数据调了很久才A。
（delt()删除模块其实是不需要重建的，不影响时间复杂度）
替罪羊树具体详见此篇知乎：替罪羊树
AC Code
#include "iostream"
#include "cstdio"
#define alpha 0.7
using namespace std;
struct ScapeGoatTree{
int lc,rc,n,w,s,fa;
}a[];
struct REbuild{
int n,w;
}d[];
void rebuild(int p);
int tot=,tott=,top=,h[],n,T,X,root;
int check(int p){
if(a[p].w==)return ;
if ((a[a[p].lc].s+a[a[p].lc].w>=double(alpha*(a[p].w+a[p].s)))||
(a[a[p].rc].s+a[a[p].rc].w>=double(alpha*(a[p].w+a[p].s))))return ;
return ;
}
int getN(int x){
int now=root;
while(a[now].n!=x&&a[now].s!=){
if(a[now].n>=x)now=a[now].lc;
else now=a[now].rc;
}
return now;
}
void insr(int x,bool rb){
if(root==){
root=;
a[].n=x;
a[].w++;
return;
}
int now=root;
while(a[now].s!=){
if(x==a[now].n){
a[now].w++;
return;
}
if(x>a[now].n&&a[now].rc==)break;
if(x<a[now].n&&a[now].lc==)break;
a[now].s++;
if(x>a[now].n)now=a[now].rc;
else if(x<a[now].n)now=a[now].lc;
} if(x==a[now].n){
a[now].w++;
return;
}
a[now].s++;
int tmp=now;
if(x>a[now].n)now=a[now].rc=++tot;
else if(x<a[now].n)now=a[now].lc=++tot;
a[now].w++;
a[now].n=x;
if(tmp!=now)a[now].fa=tmp;
int chk=;
while(now!=root){
now=a[now].fa;
if(check(now))chk=now;
}
if(rb)rebuild(chk);
}
int getnewp(){
if(top>){
top--;
return h[top+];
}
else return ++tot;
}
void dfs(int p){
h[++top]=p;
if(a[p].lc!=)dfs(a[p].lc);
if(a[p].w!=)d[++tott].n=a[p].n,
d[tott].w=a[p].w;
a[p].s=;
if(a[p].rc!=)dfs(a[p].rc);
}
void make(int l,int r,int p,int fa){
int mid=(l+r)/;
a[p].fa=fa;
a[p].w=d[mid].w;
a[p].n=d[mid].n;
if(mid->=l)a[p].lc=getnewp(),make(l,mid-,a[p].lc,p);else a[p].lc=;
if(mid+<=r)a[p].rc=getnewp(),make(mid+,r,a[p].rc,p);else a[p].rc=;
a[p].s=a[a[p].lc].w+a[a[p].lc].s+a[a[p].rc].w+a[a[p].rc].s;
}
void rebuild(int p){
if(p==)return;
tott=;
dfs(p);
int now=getnewp();
a[now].fa=a[p].fa;
if(p==root)root=now;
int mid=(+tott)/;
if(d[mid].n>a[a[p].fa].n)a[a[p].fa].rc=now;
else a[a[p].fa].lc=now;
make(,tott,now,a[p].fa);
}
void delt(int p,bool rb){
a[p].w--;
int chk=;
while(p!=root){
p=a[p].fa;
a[p].s--;
if(check(p))chk=p;
}
// if(rb)rebuild(chk);
}
int XgetRk(int x);
int RkgetX(int x);
int suc(int x){
insr(x+,);
int tmp=XgetRk(x+),nx=getN(x+);
delt(nx,);
return RkgetX(tmp);
}
int pre(int x){
insr(x,);
int tmp=XgetRk(x);
delt(getN(x),);
return RkgetX(tmp-);
}
int XgetRk(int x){
int p=getN(x),ans;
ans=a[a[p].lc].s+a[a[p].lc].w;
while(p!=root){
if(a[a[p].fa].rc==p)ans+=a[a[a[p].fa].lc].s+a[a[a[p].fa].lc].w+a[a[p].fa].w;
p=a[p].fa;
}
return ans+;
}
int RkgetX(int x){
int now=root;
while(true){
int lcS=a[a[now].lc].s+a[a[now].lc].w;
if(x<=lcS)now=a[now].lc;
else if(x>lcS&&x<=a[now].w+lcS)return a[now].n;
else x-=lcS+a[now].w,now=a[now].rc;
if(x==)return a[now].fa;
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
if(i%==){
int ttott;
ttott++;
}
scanf("%d%d",&T,&X);
if(T==)insr(X,);
else if(T==)delt(getN(X),);
else if(T==)printf("%d\n",XgetRk(X));
else if(T==)printf("%d\n",RkgetX(X));
else if(T==)printf("%d\n",pre(X));
else if(T==)printf("%d\n",suc(X));
}
}