椰子 题解

· · 个人记录

以下是官方题解：

首先看懂题后可以获得一个十分简单的暴力做法：

枚举那个被修改的数字，然后枚举每一个区间，计算区间 \gcd，看有多少不同的值即可。

时间复杂度为 O(n^4\log n) 或精细实现可以做到 O(n^3\log n)。分别可以通过前两个 subtask。

然后考虑一个比较送的性质 A，用上面的代码打表可以很快发现答案是 n,n-1,n-1,...。

送分结束。

首先我们应该发现一件事，对于每个答案，它都必然是 n 或 n-1。原因是假如我们把值为 x 的数改成了 1，那么对于剩下 n-1 个数肯定是没有任何变化的，于是我们可以把这 n-1 个数看作 n-1 个长度为 1 的区间，选择它们即可。于是答案的下界一定是 n-1，答案是否为 n 仅仅只用考虑是否有一个区间的 \gcd 为 x 即可。

问题变为判断：在区间不经过值为 x 的数的情况下，是否有一个区间的 \gcd 为 x。我们去枚举 x，然后一个一个判断。

既然要使得一个区间 \gcd 为 x，那么这个区间内的所有数都必然是 x 的倍数，而且由于 \gcd 一定单调不减且下限为 x 。于是我们只用扫描整个序列，找到所有值为 x 倍数的极大的区间（极大的指的是不可再左右拓展），计算其 \gcd，查看是否存在一个区间 \gcd 值为 x 即可。时间复杂度 O(n^2\log n)。

我们考虑优化刚刚的整个过程，由于每次都要扫描整个序列，而序列中不是 x 倍数的地方是完全没用的，这浪费了很多时间。于是我们每次直接枚举 x 的所有倍数，预处理 pos_i 表示值为 i 的数的位置，于是可以找到所有这些数的位置。初始时认为每个数就是一个长度为 1 的区间，然后依次加入一个 kx ，查看它的左右的数是否也为 x 的倍数，如果是，则用 kx 合并左右两个数所在的区间。这个过程可以用并查集轻松实现，当然，也可以直接把这些位置排序然后取出连续段计算。

现在我们来分析这个做法的复杂度，对于每一轮到 x，会有 \dfrac{n}{x} 个位置要考虑，每个位置最多合并 O(1) 次，合并的复杂度为 O(\log n)，所以复杂度就是 \sum\limits_{x=1}^n \dfrac{n}{x}\log n=\log n\sum\limits_{x=1}^n \dfrac{n}{x}。用调和级数近似一下就是 O(n\log^2 n)，可以通过本题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,a[500001],pos[500001];
int fa[500001],val[500001]; 
int find(int x){ //并查集 
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){ //合并两段
    x=find(x),y=find(y);
    if(x==y) return ;
    val[y]=__gcd(val[x],val[y]); //更新这一段的 gcd 值 
    fa[x]=y;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]]=i;
    }
    for(int i=1;i<=n;i++) fa[i]=i,val[i]=a[i];
    cout<<n<<' ';//改 1 没有影响，答案一定是 n 
    for(int i=2;i<=n;i++){ //求解修改 i 时的答案 
        int ans=n+1;
        for(int j=i+i;j<=n;j+=i){
            int x=pos[j];
            if(x!=1&&a[x-1]%i==0&&a[x-1]!=i) merge(x-1,x); //可以和左右合并就直接合并两个 i 的倍数构成的块 
            if(x!=n&&a[x+1]%i==0&&a[x+1]!=i) merge(x+1,x);
            ans=min(ans,val[find(x)]); //查询当前情况 i 的倍数段中最小的 gcd 值 
        }
        if(ans==i) cout<<n<<' '; //gcd可以为 i 
        else cout<<n-1<<' ';
        for(int j=i+i;j<=n;j+=i) fa[pos[j]]=pos[j],val[pos[j]]=j; // 清空
    }
}