洛谷P3402 【模闆】可持久化并查集（可持久化線段樹，線段樹，并查集）

orz TPLY 巨佬，題解講的挺好的。

這裡重點梳理一下思路，做一個小小的補充吧。

寫可持久化線段樹，葉子節點維護每個位置的fa，利用每次隻更新一個節點的特性，每次插入\(logN\)個節點，這一部分思路還是很輕松。關于此部分的其它問題可以參考下我的可持久化線段樹總結

一開始，寫慣了正常并查集、用慣了路徑壓縮的我，以為在這一題裡也要這麼搞。我對我的naive真是太感動了

試想一下，因為路徑壓縮時，再次調用getf後，是要更新一部分值的。在數組上搞這些操作倒是挺快，然而在可持久化線段樹裡呢？每次找一個fa要\(log\)次，把這個節點更新又要建立log個節點，一共要循環找不滿log次，理論上時間複雜度是\(O(Mlog^2N)\)的，但空間也是O\((Mlog^2N)\)的啊，乘個系數\((Mlog^2N×sizeof(int)×4\approx 800MB\),實際不滿\()\)，随便算算就要炸空間了。。。。。。

那怎麼辦？去掉路徑壓縮不就得啦！并查集的按秩合并也是很優秀的方法，每次getf也隻需要\(log\)次！時間複雜度\(O(Mlog^2N)\)并沒有變。然後每次合并時隻需要更新一個點，空間不就省下來了麼？空間複雜度\(O(MlogN)\)。

以下是代碼，數組版，葉子節點資訊用結構體放了一下，略省點空間吧。。。

太弱了，不會封裝，非遞歸版，可能略醜，見諒

#include<cstdio>
#define R register int
#define gc while(*++p<'0')
#define in(z) gc;z=*p&15;while(*++p>='0')z*=10,z+=*p&15
#define copy(id) lc[rt[i]=++cnt]=lc[rt[id]],rc[cnt]=rc[rt[id]];
//直接複制版本，不做改動
const int N=200009,M=4000009;
char I[M];
int n,i,cnt,cntl,rt[N],lc[M],rc[M],pos[M];
//cnt線段樹節點，cntl葉子節點，pos記錄對應葉子節點在數組中的位置
struct LEAF{
    int fa,dep;
}leaf[N<<2];//葉子節點資訊，dep用于按秩合并
inline LEAF*getf(R k){
    R u,l,r,m;
    while(1){
        u=rt[i-1],l=1,r=n;
        while(l<r)
        {
            m=(l+r)>>1;
            if(k<=m)r=m,u=lc[u];
            else  l=m+1,u=rc[u];
        }
        if(k==leaf[pos[u]].fa)break;
        k=leaf[pos[u]].fa;//循環找fa
    }
    return&leaf[pos[u]];//傳回指針友善後續操作
}
void build(R&u,R l,R r){//建初始線段樹
    u=++cnt;
    if(l==r){
        leaf[pos[u]=++cntl]=(LEAF){l,0};
        return;
    }
    R m=(l+r)>>1;
    build(lc[u],l,m),build(rc[u],m+1,r);
}
inline void insert(R*u,R v,R k,LEAF newl){//更新節點
    R l=1,r=n,m;
    while(l<r)	{
        *u=++cnt;
        m=(l+r)>>1;
        if(k<=m)r=m,rc[*u]=rc[v],u=&lc[*u],v=lc[v];
        else  l=m+1,lc[*u]=lc[v],u=&rc[*u],v=rc[v];
    }
    leaf[pos[*u=++cnt]=++cntl]=newl;
}
int main(){
    fread(I,1,sizeof(I),stdin);
    register char*p=I-1;
    register LEAF*af,*bf,*tmp;
    R m,a,b;
    in(n);in(m);
    build(rt[0],1,n);
    for(i=1;i<=m;++i){
        gc;
        switch(*p){
        case '1':in(a);in(b);
            af=getf(a),bf=getf(b);
            if(af->fa==bf->fa){copy(i-1);break;}//已合并，跳過操作
            if(af->dep>bf->dep)tmp=af,af=bf,bf=tmp;//按秩合并，确定bf為深度更大的
    		insert(&rt[i],rt[i-1],af->fa,(LEAF){bf->fa,af->dep});
            if(af->dep==bf->dep)insert(&rt[i],rt[i],bf->fa,(LEAF){bf->fa,bf->dep+1});//注意更新深度
            break;
        case '2':in(a);copy(a);break;
        case '3':in(a);in(b);copy(i-1);
            putchar((getf(a)->fa==getf(b)->fa)|'0');
            putchar('\n');
        }
    }
    return 0;
}