P3369 【模板】普通平衡树 替罪羊树解法

P3369 【模板】普通平衡树

#include
#include
#include
#include
#define lc ch[p][0]
#define rc ch[p][1]
using namespace std;
const int N=100010;
const int inf=0x3f3f3f3f;
const double alpha=0.75;
int n,m;
int rt=1,tot=1;
int loc[N],sum;
int ch[N][2],fa[N];
double siz[N];
int val[N];
inline void pushup(int p){
    siz[p]=siz[lc]+siz[rc]+1;
}
inline bool banlc(int p){
    if(siz[lc]>siz[p]*alpha) return 0;
    if(siz[rc]>siz[p]*alpha) return 0;
    return 1;
}
void build(int &p,int L,int R){
    if(L>R){
        p=0;    
        return;
    }
    int mid=(L+R)>>1;
    p=loc[mid];
    build(lc,L,mid-1);
    build(rc,mid+1,R);
    if(lc) fa[lc]=p;
    if(rc) fa[rc]=p;
    pushup(p);
}
void DFS(int p){
    if(!p) return;
    if(lc) DFS(lc);
    loc[++sum]=p;
    if(rc) DFS(rc);
}
void rebuild(int p){
    sum=0;
    DFS(p);
    int f0=fa[p];
    bool b=(ch[f0][0]!=p);
    int cur;
    build(cur,1,sum);
    fa[cur]=f0;
    ch[f0][b]=cur;
    if(p==rt) rt=cur;
}
void ins(int v){
    int p=rt,cur=++tot;
    siz[cur]=1;
    val[cur]=v;
    bool b;
    while(1){
        siz[p]++;
        b=(v>=val[p]);
        if(ch[p][b]) p=ch[p][b];
        else{
            ch[p][b]=cur;
            fa[cur]=p;
            break;
        }
    }
    int pos=0;
    for(int i=cur;i;i=fa[i]){
        if(!banlc(i)) pos=i;
    }
    if(pos) rebuild(pos);
}
inline int getpos(int p,int v){
    while(1){
        if(val[p]==v) return p;
        if(v>val[p]) p=rc;
        else p=lc;
    }
}
inline void del(int v){
    int p=getpos(rt,v);
    if(lc&&rc){
        int cur=lc;
        while(ch[cur][1]) cur=ch[cur][1];
        val[p]=val[cur];
        p=cur; 
    }
    int son=lc?lc:rc;
    int f0=fa[p];
    bool b=ch[f0][0]!=p;
    ch[f0][b]=son;
    fa[son]=f0;
    for(int i=fa[p];i;i=fa[i]) siz[i]--;
    if(p==rt) rt=son;
}
inline int getrank(int p,int v){
    int ret=0;
    while(p){
        if(v>val[p]) ret+=siz[lc]+1,p=rc;
        else p=lc;
    }
    return ret;
}
inline int kth(int p,int k){
    while(1){
        if(k<=siz[lc]) p=lc;
        else if(k==siz[lc]+1) return p;
        else k-=siz[lc],k--,p=rc;
    }
}
inline int getpre(int p,int v){
    int ret=-inf;
    while(p){
        if(v>val[p]) ret=max(ret,val[p]),p=rc;
        else p=lc;
    }
    return ret;
}
inline int getsuc(int p,int v){
    int ret=inf;
    while(p){
        if(v