题解 P3835 【【模板】可持久化平衡树】

BFqwq · 2020-02-26 17:08:37 · 题解

看了一篇题解区，这题的比较主流的几种解法分别是 FHQ-Treap，线段树，01-Trie 和替罪羊树。

为什么 WBLT 这么好写却一篇题解都没有qaq

考虑 WBLT 的性质，在修改的时候操要是不 maintain，全树的形态除了叶结点是不会有变化的。

同样，在删除的时候，只要不 maintain，全树的形态也不会有变化。

因此考虑将 maintain 操作叠加起来，放在修改完成后再一遍进行。

只要碰到 maintain 操作，我们就新建一个节点，然后在操作时递归向下。

int maintain(int o){
    int nw=nnd(t[o].v,t[o].w,t[o].ls,t[o].rs);
    if(t[t[nw].ls].w>t[t[nw].rs].w*ratio){
        t[nw].ls=maintain(t[nw].ls);
        t[nw].rs=maintain(t[nw].rs);
        t[nw].rs=merge(t[t[nw].ls].rs,t[nw].rs);
        t[nw].ls=t[t[nw].ls].ls;
    }
    if(t[t[nw].rs].w>t[t[nw].ls].w*ratio){
        t[nw].ls=maintain(t[nw].ls);
        t[nw].rs=maintain(t[nw].rs);
        t[nw].ls=merge(t[nw].ls,t[t[nw].rs].ls);
        t[nw].rs=t[t[nw].rs].rs;
    }
    return nw;
}

由于在实际操作的时候一共只加了一个节点，并不会对很多节点的子树大小关系产生影响。

可以证明，每次修改最多只需对 \log 个节点（即链上的节点）进行 maintain 操作。

顾在修改时时间复杂度为 \log n，最坏空间复杂度也是 \log n。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
char cr[200];int tt;
inline void print(int x,char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=500010;
const int ratio=4; 
struct lef{
    int v,w,ls,rs;
}t[maxn*200];
int rt[maxn],tot;
int nnd(int v,int w,int ls,int rs){
    t[++tot]=(lef){v,w,ls,rs};
    return tot;
}
int merge(int x,int y){
    return nnd(t[y].v,t[x].w+t[y].w,x,y);
}
void pushup(int o){
    if(!t[t[o].ls].w){
        return;
    }
    t[o].w=t[t[o].ls].w+t[t[o].rs].w;
    t[o].v=t[t[o].rs].v;
}
int maintain(int o){
    int nw=nnd(t[o].v,t[o].w,t[o].ls,t[o].rs);
    if(t[t[nw].ls].w>t[t[nw].rs].w*ratio){
        t[nw].ls=maintain(t[nw].ls);
        t[nw].rs=maintain(t[nw].rs);
        t[nw].rs=merge(t[t[nw].ls].rs,t[nw].rs);
        t[nw].ls=t[t[nw].ls].ls;
    }
    if(t[t[nw].rs].w>t[t[nw].ls].w*ratio){
        t[nw].ls=maintain(t[nw].ls);
        t[nw].rs=maintain(t[nw].rs);
        t[nw].ls=merge(t[nw].ls,t[t[nw].rs].ls);
        t[nw].rs=t[t[nw].rs].rs;
    }
    return nw;
}
int find(int o,int k) {
    if(t[o].w==1) return 1;
    if(k<=t[t[o].ls].v)return find(t[o].ls,k);
    else return t[t[o].ls].w+find(t[o].rs,k);
}
int select(int o,int k) {
    if(t[o].w==1) return t[o].v;
    if(k<=t[t[o].ls].w)return select(t[o].ls,k);
    else return select(t[o].rs,k-t[t[o].ls].w);
}
int insert(int o,int x){
    int nw=nnd(t[o].v,t[o].w,t[o].ls,t[o].rs);
    if(t[nw].w==1){
        t[nw].ls=nnd(min(t[nw].v,x),1,0,0);
        t[nw].rs=nnd(max(t[nw].v,x),1,0,0);
    }
    else if(x>t[t[nw].ls].v)
        t[nw].rs=insert(t[nw].rs,x);
    else 
        t[nw].ls=insert(t[nw].ls,x);
    pushup(nw);
    return nw;
}
int erase(int o,int x){
    int nw=nnd(t[o].v,t[o].w,t[o].ls,t[o].rs);
    if(t[nw].w==1&&t[nw].v!=x)
        return nw;
    else if(t[t[nw].ls].w==1&&t[t[nw].ls].v==x)
        nw=t[nw].rs;
    else if(t[t[nw].rs].w==1&&t[t[nw].rs].v==x)
        nw=t[nw].ls;
    else if(x>t[t[nw].ls].v)
        t[nw].rs=erase(t[nw].rs,x);
    else 
        t[nw].ls=erase(t[nw].ls,x);
    pushup(nw);
    return nw;
}
signed main(){
    int n=read();
    rt[0]=nnd(2147483647,1,0,0);
    for(int i=1;i<=n;i++){
        int wh=read(),opt=read(),x=read();
        if(opt==1){
            rt[i]=maintain(insert(rt[wh],x));
        }
        if(opt==2){
            rt[i]=maintain(erase(rt[wh],x));
        }
        if(opt==3){
            print(find(rt[wh],x));
            rt[i]=rt[wh];
        }
        if(opt==4){
            print(select(rt[wh],x));
            rt[i]=rt[wh];
        }
        if(opt==5){
            int rk=find(rt[wh],x);
            if(rk==1)print(-2147483647);
            else print(select(rt[wh],rk-1));
            rt[i]=rt[wh];
        }
        if(opt==6){
            int rk=find(rt[wh],x+1);
            print(select(rt[wh],rk));
            rt[i]=rt[wh];
        }
    }
    return 0;
}