记录一类分治方法

鲤鱼江 · 2025-10-14 21:04:59 · 算法·理论

可能会放三个题，感觉难度严格递减。

会放一些我以前会的屑做法（？），比较烂应该没啥启发性。

注意：大部分时候你需要忽略孤立点来保证正确性！

嗯放了第三个题是为了让你明白这个做法可能时空上会稍微劣一点，有其他选择就别写了吧。不过你不觉得这种重构树很好看嘛。

UPD：

大家可以去看一下，有类似的地方且感觉比我这篇文章深刻一点。

题一

弱化版

给定 n 个点 m 条边的一张有权无向图，有 q 次操作，操作包含：加删边，修改一条边的权值，求当前最小生成树，或报告无解。

1\le n,m,q\le 10^5

Sayaka 都能看懂的做法其一

我们知道加边求最小生成树是可以 LCT 的，规避删边的有力做法就是线段树分治，明显支持撤销（把断掉的边连回来即可），可以做到大常数 O(n\log^2 n)。

码力惊人可以尝试。

:::warning[昨年实现的屑代码]

struct Oper{
    int opt,x,y;//opt=0:需要link,opt=1:需要cut
    Oper(int opt=0,int x=0,int y=0):
        opt(opt),x(x),y(y){;}
}stk[N<<2];
int top,Ans,Res[N],n,m,k,las[N];

struct LCT{
    struct node{
        int ch[2],fa,val,ans,tag;
        #define ch(k,i) tr[k].ch[i]
        #define val(k) tr[k].val
        #define ans(k) tr[k].ans
        #define tag(k) tr[k].tag
        #define fa(k) tr[k].fa
    }tr[N];
    int tot,Son[N][2];

    LCT(){val(0)=-1e9;}

    inline bool isroot(const int &k){return (k!=ch(fa(k),0))&&(k!=ch(fa(k),1));}
    inline int Max(const int &x,const int &y){return val(x)>val(y)?x:y;}
    inline void rever(const int &k){swap(ch(k,0),ch(k,1));tag(k)^=1;}
    inline bool chk(const int &k){return k==ch(fa(k),1);}
    inline void pushdown(const int &k){
        if(!tag(k)) return ;
        rever(ch(k,0));
        rever(ch(k,1));
        tag(k)=0;
    }
    inline void Alldown(const int &k){
        if(!isroot(k)) Alldown(fa(k));
        pushdown(k);
    }
    inline void pushup(int k){ans(k)=Max(k,Max(ans(ch(k,0)),ans(ch(k,1))));}
    inline void rotate(const int &x){
        int y=fa(x),z=fa(y);
        int fg=chk(x),w=ch(x,!fg);
        ch(x,!fg)=y;ch(y,fg)=w;
        if(!isroot(y)) ch(z,chk(y))=x;
        fa(x)=z;fa(y)=x;fa(w)=y;
        pushup(y);pushup(x);
    }
    void splay(int x){
        Alldown(x);
        while(!isroot(x)){
            int y=fa(x);
            if(!isroot(y)) rotate((chk(x)==chk(y))?y:x);
            rotate(x);
        }
    }
    inline int newnode(int v=-1e9){++tot;val(tot)=v;ans(tot)=tot;return tot;}
    inline void init(const int n){for(int i=1;i<=n;++i) newnode();}
    inline void access(int x){for(int y=0;x;x=fa(y=x))splay(x),ch(x,1)=y,pushup(x);}
    inline void makeroot(int x){access(x);splay(x);rever(x);}
    inline void split(int x,int y){makeroot(x);access(y);splay(y);}
    inline void link(int x,int y){makeroot(x);fa(x)=y;}
    inline void cut(int x,int y){split(x,y);fa(x)=ch(y,0)=0;pushup(y);}
    inline int findroot(int x){
        access(x);splay(x);
        while(ch(x,0)) pushdown(x),x=ch(x,0);
        splay(x);return x;
    }
    inline bool same(int x,int y){
        makeroot(x);
        return findroot(y)==x;
    }
    inline void connect(int x,int y,int z){
        if(!same(x,y)){
            int now=newnode(z);
            stk[++top]=Oper(1,x,now);
            stk[++top]=Oper(1,y,now);
            link(x,now);link(now,y);
            Son[now][0]=x;
            Son[now][1]=y;
            Ans+=z;return ;
        }
        split(x,y);int tmp=ans(y);
        if(val(tmp)>z){
            int now=newnode(z);
            makeroot(tmp);
            stk[++top]=Oper(0,tmp,Son[tmp][0]);
            stk[++top]=Oper(0,tmp,Son[tmp][1]);
            cut(tmp,Son[tmp][0]);
            cut(tmp,Son[tmp][1]);
            fa(tmp)=tag(tmp)=0;ans(tmp)=tmp;
            link(x,now);link(now,y);
            stk[++top]=Oper(1,x,now);
            stk[++top]=Oper(1,y,now);
            Son[now][0]=x;Son[now][1]=y;
            Ans+=z-val(tmp);
        }
    }
}t;

#define ls now<<1
#define rs now<<1|1
struct edge{
    int x,y,z;
    edge(int x=0,int y=0,int z=0):
        x(x),y(y),z(z){;}
}a[N];
vector < edge > v[N];

void update(int now,int l,int r,int x,int y,const edge &c){
    if(x>y) return ;
    if(x<=l&&r<=y){v[now].emplace_back(c);return ;}
    int mid=(l+r)>>1;
    if(mid>=x) update(ls,l,mid,x,y,c);
    if(mid<y) update(rs,mid+1,r,x,y,c);
}

void Search(int now,int l,int r){
    int res=Ans,ed=top;
    for(auto i:v[now]) t.connect(i.x,i.y,i.z);
    if(l==r) Res[l]=Ans;
    else {
        int mid=(l+r)>>1;
        Search(ls,l,mid);
        Search(rs,mid+1,r);
    }
    Ans=res;
    while(top!=ed){
        Oper z=stk[top--];
        if(z.opt==0) t.link(z.x,z.y);
        else t.cut(z.x,z.y);
    }
}

:::

Sayaka 也能看懂的做法其二

发现离线的情况下加删边是唬人的，我们只需要考虑修改边的权值就行了。

考虑操作分块，对于每个块处理询问即可，非常愚蠢。

视实现可以做到 O(n\sqrt n) 到 O(n\sqrt n\log n)。

正常版

我们期待一种时间复杂度优秀的做法。

分治

发现离线的情况下加删边是唬人的，我们只需要考虑修改边的权值就行了。

设被修改过的边集为 Q，全集为 E。

将 Q 中的边权值设为 -\inf，和 E-Q 中的边跑一遍最小生成树。

那么权值非 -\inf 且在最小生成树上的边具有不可替代性，直接将这些边所连接的节点缩起来，顺便给点重新标号一下。

不难注意到，点数变成 O(|Q|) 级别了，但是边数是 O(n-|Q|) 级别的。

再把 Q 中的边权值设为 +\inf，和剩下缩完点的边跑一遍最小生成树，把权值非 +\inf 且不在最小生成树上的边全部删掉，这些边肯定没用。

现在边数和点数都是 O(|Q|) 级别了。

你可能会说，为什么我们要干这些事，n,|Q| 不是同阶吗。

我们敏锐地注意到，这下可以分治了。

向左边分治可以直接递归处理 [1,|Q|/2] 的操作和询问，向右边分治的时候把在左边出现过的边加到 E 里边，再向右边递归，明显此时 |E|\le 1.5|Q|。

明显每次递归的时候 n,|E|,|Q| 是同阶的，精细实现可以做到较小常数的 O(n\alpha(n)\log n)。

本质

笔者了解到做法之后感到有点反直觉，思考我们凭什么能将点边都化到 O(|Q|) 级别，复杂度又为什么是对的。

本质在于：在于分治过程中，一棵分治树最多只有 q 种操作，而大部分问题只有 q 种操作的情况下，都只能区分出 q+1 情况，所以我们可以只考虑这 q+1 个需要考虑的部分。

而剩下不需要区分的情况可以根据之前得到的已知信息直接处理，由此只考虑 q+1 种需要区分的情况就是对的。

不难发现操作分块做法可以用这个 trick 做到 O(n\sqrt n\alpha(n))。

感觉剥离处本质之后会发现本做法拓展性似乎很强！

比如你在数轴上放 m 个点只会把数轴分成 m+1 段。

题二

转化后的题目

给定一张有向图，要求支持加边和查询一条边什么时候被缩进一个强连通分量中。

这个倒是老生常谈了。

做法

考虑分治。

我们将 \le mid 时刻被加入的边拿出来跑 tarjan 缩点，看上去很错，但是下面的操作保证了加入的边数是正确的。

将两端点在同一个强连通分量的边丢到左边去，不在一个强连通分量中的边丢到右边去，记得给每条边重新标号。

这样可以保证加入的边数是正确的。

这样是 O(m\log m) 的。

实际上加入的是被丢到这个递归函数的边中时刻 \le mid 的边。

:::warning[屑代码]

inline void add(int x,int y){v[x].emplace_back(y);}
void Binary(int l,int r,vector<node> &c){
    if(c.empty()) return ;
    if(l==r){for(auto x:c) g[l].emplace_back(a[x.bid]);return ;}
    int mid=(l+r)>>1;
    vector<node> L,R;tot=idx=top=0;
    for(auto x:c) (x.id<=mid)&&(add(x.x,x.y),0);
    for(auto x:c) if(!dfn[x.x]) tarjan(x.x);
    for(auto x:c){
        if(!bel[x.x]) bel[x.x]=++tot;
        if(!bel[x.y]) bel[x.y]=++tot;
        if(bel[x.x]==bel[x.y]&&x.id<=mid) L.emplace_back(node(x.x,x.y,x.id,x.bid));
        else R.emplace_back(node(bel[x.x],bel[x.y],x.id,x.bid));
    }
    for(auto x:c){dfn[x.x]=dfn[x.y]=bel[x.x]=bel[x.y]=vis[x.x]=vis[x.y]=0;v[x.x].clear();}
    Binary(l,mid,L);Binary(mid+1,r,R);
}

:::

这个做法的本质也是通过手法控制递归时的点数和边数来保证合法性。你可以注意到某些边丢到右边去是很蠢的，只需要过程中带来的强连通性丢下去就行了。

题三

题意

给定 n 个点的无向图，有 m 次加边，加边完成后有 q 次询问，求两个点什么时候被缩进一个双连通分量。

这个题不是分治题。

Sayaka 也能看懂的做法

直接使用题二的分治方法，求出每条边什么时候被缩进双连通分量，然后可以建出一个最小生成树，每次直接倍增查询路径最小值，很好写。

更加优秀的做法

考虑直接根据每条边加入的时间建出最小生成树，然后拿出所有非树边，那么每条非树边都会导致一条链上的节点被搞进一个双连通分量。

我们可以类似 Kruskal 重构树，建出边双连通重构树。

具体地，对每个点维护一个并查集，存：自己这个双连通分量里最浅的节点是哪个，对应的双连通重构树的根是什么。

每次合并一条链的时候新建一个节点，然后跳并查集，把所有途经节点的双连通重构树的根连到新建节点上。

最后查询两个节点什么时候被缩进一个双连通分量，只需要求一下在双连通重构树上的 LCA 就做完了。