题解：P12579 [UOI 2021] 哥萨克与 GCD

NyaingCBC · 2026-11-13 14:49:52 · 题解

思路分析

纯观察。

考虑进行图论建模。询问 \sum_{i=l}^rb_i 就是询问 s_r-s_{l-1}，其中 s_n=\sum_{i=1}^nb_i，且已知 s_0=0。目标等价于确定所有的 s。

于是我们会询问恰好 n 次，每一次的边 (l-1,r) 恰好形成了树，树边的代价就是 \gcd(a_l,\dots,a_r)，于是就是在问我们最小生成树的权值之和。

考虑最终的图中有 (0,n) 这条边一定是不劣的：直接按照 kruskal 的方法建图，不难发现 (0,n) 这条边的边权一定是全局最小值。

此时考虑，如果有一个生成树的树中有边 (i,j)，那么根据连通性将这个边调整为 (0,j) 或者 (i,n) 一定是不劣的。这是因为 \gcd(a,b,\dots)=\gcd(a,\gcd(b,\dots))，并且 \gcd(a,b)\le a，于是 v(i,n),v(0,j)\le v(i,j)。

从而，我们得知最终的树一定只会包含 (0,i) 和 (i,n) 两种边。又因为 v(0,i) 是单调递减的，v(i,n) 是单调递增的，所以 [1,n-1] 中的点一定是前面一部分和 n 连，后面一部分和 1 连。

此外，我们还注意到，v(0,i+1)=\gcd(v(0,i),a_{i+1})，因此 v(0,i) 一定只出现了 a_1 的一个“因数下降链”。而由于每一次都是变成真因数，至少砍半，因此不同的 v(0,i) 的数值一定也只有 O(\log) 个。

我们考虑使用线段树二分来快速查找 v(0,i) 的极长连续段。具体来说，v(0,j)=v(0,i) 等价于 \gcd(a_{i+1},\dots,j) 是 v(0,i) 的倍数。于是我们直接在线段树上面维护 [l,r] 的区间 \gcd 就可以实现线段树二分了。

因此，我们可以 O(\log^2) 的把两种数值的所有区间与值都给求出来，直接从前到后一遍扫过去累加最小值就行了。这一步只有 O(\log n)。

而对于修改，就是一路向上重算区间 \gcd。由于求 \gcd 还有一个 \log，所以时间复杂度也是 O(\log^2) 的。

综上，此题可解，时间复杂度 O(n\log^2 n)。实现的时候属于是做题做傻了，套了一个差分，不过也说明这道题可以支持区间加。参考代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr bool online=0;
int n,m,a[100005];
inline int gcd(int l,int r){ return r?gcd(r,l%r):l; }
struct seg_tree{
    struct node{ int l,r,v; }re[100005<<2];
    inline void build(int l,int r,int p){
        re[p].l=l; re[p].r=r;
        if(l==r)return void(re[p].v=abs(a[l+1]-a[l]));
        build((l+r>>1)+1,r,p<<1|1);
        build(l,(l+r>>1),p<<1);
        re[p].v=gcd(re[p<<1].v,re[p<<1|1].v);
    }
    inline void set(int cp,int cv,int p){
        if(re[p].l==re[p].r) return void(re[p].v=cv);
        set(cp,cv,p<<1|(cp>re[p<<1].r));
        re[p].v=gcd(re[p<<1].v,re[p<<1|1].v);
    }
    inline int fnxts(int v,int p){
        if(!(re[p].v%v)) return 0;
        if(re[p].l==re[p].r) return re[p].l;
        if(re[p<<1].v%v) return fnxts(v,p<<1);
        return fnxts(v,p<<1|1);
    }
    inline int fnxt(int l,int v,int p){
        if(re[p].l>=l) return fnxts(v,p);
        if(l<=re[p<<1].r&&re[p<<1].v%v){
            int ret=fnxt(l,v,p<<1);
            if(ret) return ret;
        }
        return fnxt(l,v,p<<1|1);
    }
    inline int fpres(int v,int p){
        if(!(re[p].v%v)) return 0;
        if(re[p].l==re[p].r) return re[p].l;
        if(re[p<<1|1].v%v) return fpres(v,p<<1|1);
        return fpres(v,p<<1);
    }
    inline int fpre(int r,int v,int p){
        if(re[p].r<r) return fpres(v,p);
        if(r>re[p<<1|1].l&&re[p<<1|1].v%v){
            int ret=fpre(r,v,p<<1|1);
            if(ret) return ret;
        }
        return fpre(r,v,p<<1);
    }
}sgt;
vector<pair<int,int>>va0,van;
inline int solve(){
    va0.clear(); van.clear();
    for(int i=1,v=a[1];;){
        va0.emplace_back(i,v);
        if(v==1) break;
        i=sgt.fnxt(i,v,1)+1;
        v=__gcd(v,a[i]);
    }
    for(int i=n,v=a[n];;){
        van.emplace_back(i,v);
        if(v==1) break;
        i=sgt.fpre(i,v,1);
        v=__gcd(v,a[i]);
    }
    for(int i=1;i!=van.size();++i)
        van[i-1].first=van[i].first+1;
    if(!van.back().first) van.pop_back();
    else van.back().first=1;
    if(va0.back().first>n) va0.pop_back();
    reverse(van.begin(),van.end());
    va0.emplace_back(n+1,1e12);
    van.emplace_back(n+1,1e12);
    van.emplace_back(n+2,1e12);
    for(auto&v:van) v.first--;
    van[0].first++;
    if(van[0].first==van[1].first)
        van.erase(van.begin());
    // for(const auto&v:va0) cerr<<v.first<<" "<<v.second<<endl;
    // for(const auto&v:van) cerr<<v.first<<" "<<v.second<<endl;
    int ret=0;
    for(int p0=0,pn=0,ps=1;ps<=n;){
        if(va0[p0+1].first<van[pn+1].first)
            ret+=min(va0[p0].second,van[pn].second)*(va0[p0+1].first-ps),
            p0++,ps=va0[p0].first;
        else if(va0[p0+1].first>van[pn+1].first)
            ret+=min(va0[p0].second,van[pn].second)*(van[pn+1].first-ps),
            pn++,ps=van[pn].first;
        else
            ret+=min(va0[p0].second,van[pn].second)*(van[pn+1].first-ps),
            p0++,pn++,ps=van[pn].first;
    }
    return ret;
}
signed main(){
    if(online)
        freopen("gobinum.in","r",stdin),
        freopen("gobinum.out","w",stdout);
    ios::sync_with_stdio(0); cin>>n>>m;
    /*
    套娃问题先解决子问题：给定 a,b 如何求出最小代价
    本质上就是每一次查询 s_r-s_{l-1}，求确定 s 的最小代价
    确定 s 本质上就是在运行最小生成树，即用 \gcd 的代价连接一条边
    但是我们应该如何做到 O(n\log n) 呢？

    要点在于其边权的计算公式：\gcd(a_l,...,a_r)
    由于 0 位置是确定的，而 \gcd(a_1,...,a_n) 一定是全局最小的
    因此最优解一定是包括 0~n 这条边的

    完事了我们考虑，如果某一个解中有 (i,j) 这条边，其中 i,j 不是 0,n
    那么替换成 (0,j) 或者 (i,n) 一定是不劣的
    因此最优解一定只有 (0,j) 和 (i,n) 两种边！
    因此每一个位置的代价就是 min(val(0,i),val(i,n))！
    这子问题简直是精妙的！现在我们可以 O(n\log n) 回答这个子问题了！

    考虑带修怎么做。
    我会 O(\log) 求区间 gcd，带修也行
    哦不是 log^2 的，因为 gcd 是 O(\log) 的
    这是一个经典题，差分一下就行了，不复杂
    然后我们注意到 val(0,i) 单调减，val(i,n) 单调增
    所以我们可以二分切换边界，然后尝试快速求解 val 的前缀和一类的东西

    还有一个显然的性质：最多出现 \log 种 val 的数值
    所以直接在线段树上面硬做这个东西就是 \log^3 的，不知道能不能过

    其实，我们好像有办法在 O(\log^2) 的时间复杂度内表示出来 val(0,i)
    具体来说，我们仍然是线段树二分，但是用好这个性质：
    如果 a 不是 b 的倍数，那么 \gcd(a,b)\neq b
    因此只要我们预处理出来了区间 gcd 一类的东西
    那么就可以快速判断区间内有没有出现切换
    从而，我们将寻找极长段的时间复杂度压缩到了 O(\log^2)
    而每一次修改的时间复杂度也不过是 O(\log^2) 的
    至此此题可解，时间复杂度 O((n+m)\log^2n)
    */
    for(int i=1;i<=n;++i) cin>>a[i];
    a[0]=a[n+1]=1; sgt.build(0,n,1); cout<<solve()<<'\n';
    for(int i=1,l,r;i<=m;++i){
        cin>>l>>r,a[l]=r;
        sgt.set(l,abs(a[l+1]-a[l]),1);
        sgt.set(l-1,abs(a[l]-a[l-1]),1);
        cout<<solve()<<"\n";
    }
}
//1005 passed all samples exp 100pts.