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

· · 题解

P12579 [UOI 2021] 哥萨克与 GCD

前言：

这个也是一点都想不到，太难了。

正解：

首先可以想到至少要操作 n 次才能得到 b，根据高斯消元的知识可以得到。

然后我们发现每次操作我们会知道的实际上是 s_r-s_{l-1} 的值，其中 s 表示 b 数组的前缀和。

如果我们将这次操作转换为 l-1 与 r 连了一条边，可以发现这是一个不会出现环的情况，因为如果出现了环我们其实是可以通过其他的边来推出那条多余的边的。

可以发现这不就是树吗？？？

所以原问题被转化为一个生成树的问题，但是边太多了，是完全图。

那么该怎么办呢？

可以想到一个性质，对于一个序列的最大公约数，如果我在这个序列后加数，那么最大公约数是只降不增的。

也就是说对于每个点 i 其会向最远的点建边，也就是 0 或 n。

那么可以假设 pre_i 表示 \displaystyle\gcd_{j=1}^{j=i} a_j。

那么最后的答案就是 $\displaystyle\sum_{i=0}^{n}\min(lst_i,pre_i)-\gcd_{i=1}^{n}a_i$。 减去 $\gcd_{i=1}^{n}a_i$ 这个是因为 $0$ 会向 $n$ 连边，$n$ 会向 $0$ 连边，重复了。 继续钻研。 发现 $pre_i$ 是单调不升的，$lst_i$ 是单调不降的。 那么可以二分出一个 $pos$ 满足前面的 $pre_i>lst_i$，后面的 $pre_i<lst_i$。 这样子就可以转换为两个区间的求和了。 $\displaystyle\sum_{i=0}^{pos}lst_i+\sum_{i=pos+1}^{n}pre_i

但是考虑到需要修改，我们需要快速求出这个式子。

讲起来有点复杂，直接看代码吧，代码+注释应该挺好理解的。

这里证明一个东西，是在代码里优化用到的。

对于 \displaystyle\gcd_{i=l}^{r}a_i,\gcd_{i=l+1}^{r}a_i,\gcd_{i=l+2}^{r}a_i,\dots,\gcd_{i=l}^{r}a_i 这个后缀最大公约数的数组。

其出现的不同的最大公约数的个数不超过 \log V 个，V 为 a_i 的权值范围。

\displaystyle\gcd_{i=l}^{r}a_i=\gcd(\gcd_{i=l+1}^{r}a_i,a_l)

发现 \displaystyle\gcd_{i=l}^{r}a_i \le \gcd_{i=l+1}^{r}a_i。

如果说是不同的，那么就是小于，当不同时，前者相比于后者会失去一些因子。

最劣的情况就是只失去了一个因子 2，那么每次不同的后缀最大公约数都相差 2 倍。

所以原性质得证。

#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define ll long long
using namespace std;
const ll N=1e5+5;
ll n,q,a[N],pos;
ll tr[N<<2];
ll gcd(ll a,ll b){
    if(!b) return a;
    return gcd(b,a%b);
}
void pushup(ll x){tr[x]=gcd(tr[ls(x)],tr[rs(x)]);}
void build(ll x,ll l,ll r){
    if(l==r){
        tr[x]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(ls(x),l,mid),build(rs(x),mid+1,r);
    pushup(x);
}
ll get(ll x,ll l,ll r,ll A,ll B){
    if(l==r) return l;
    ll mid=(l+r)>>1;
    ll X=gcd(A,tr[ls(x)]),Y=gcd(B,tr[rs(x)]);
    //A表示[1,l]的gcd，X表示[1,mid]的gcd
    //B表示[r,n]的gcd，Y表示[mid+1,n]的gcd
    if(X<=Y) return get(ls(x),l,mid,A,Y);
    else return get(rs(x),mid+1,r,X,B);
    //这个递归找pos还是挺容易理解的吧
}
//处理lst[i]的和，应为[0,pos]的贡献。
//这里pos不减一是因为lst[i]是从[i+1,n]算的gcd
ll query1(ll x,ll l,ll r,ll pos,ll R){
    //pos 表示二分出的位置，R表示[r,n]的gcd
    if(l==r) return gcd(tr[x],R);
    ll mid=(l+r)>>1;
    ll A=gcd(tr[rs(x)],R),B=gcd(tr[ls(x)],A);
    //那么A就是[mid+1,n]的gcd，B就是[l,n]的gcd
    if(pos<=mid) return query1(ls(x),l,mid,pos,A);//如果位置在左边，那么这个地方肯定是没有贡献的，直接递归到左边。
    else{
        //如果A==B了，就说明左区间内的gcd都一样，那么就不处理左区间了。
        //根据证明的性质可以知道不同的gcd最多只有logV次，所以是O(lognlogv)
        if(A==B) return A*(mid-l+1)+query1(rs(x),mid+1,r,pos,R);
        else return query1(ls(x),l,mid,pos,A)+query1(rs(x),mid+1,r,pos,R);
    }
}
//相同如上
ll query2(ll x,ll l,ll r,ll pos,ll L){
    if(l==r) return gcd(tr[x],L);
    ll mid=(l+r)>>1;
    ll A=gcd(tr[ls(x)],L),B=gcd(A,tr[rs(x)]);
    if(pos>mid) return query2(rs(x),mid+1,r,pos,A);
    else{
        if(A==B) return A*(r-mid)+query2(ls(x),l,mid,pos,L);
        else return query2(ls(x),l,mid,pos,L)+query2(rs(x),mid+1,r,pos,A);
    }
}
//单点更新
void update(ll x,ll l,ll r,ll id,ll val){
    if(l==r){
        tr[x]=val;
        return;
    }
    ll mid=(l+r)>>1;
    if(id<=mid) update(ls(x),l,mid,id,val);
    else update(rs(x),mid+1,r,id,val);
    pushup(x);
}
ll x,w,ans;
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    pos=get(1,1,n,0,0);
    // printf("%lld\n",pos);
    ans=query1(1,1,n,pos,0)+query2(1,1,n,pos,0)-tr[1];
    printf("%lld\n",ans);
    for(int i=1;i<=q;i++){
        scanf("%lld%lld",&x,&w);
        a[x]=w;
        update(1,1,n,x,w);
        pos=get(1,1,n,0,0);
        ans=query1(1,1,n,pos,0)+query2(1,1,n,pos,0)-tr[1];
        printf("%lld\n",ans);
    }
    return 0;
}

如果审核大大看到我这篇题解了，应该已经很晚了吧。

不要老是熬夜啦，你们审题解的速度已经够快的了。

早点睡吧qaq。