CF1632D New Year Concert 题解

· · 题解

可能更好的阅读体验
题目传送门

这道题目很妙，而且可以写题解，所以就写了一片题解。

题目大意

定义一次操作位修改一个数组任意一位。
给定一个函数 f(b_1,b_2,\dots,b_n) 为对数组进行修改使得 \forall l,r\in[1,n] 使得 \gcd(a_l,a_{l+1},\dots,a_r)\not= r-l+1 的操作数次数。
现在给定一个长度为 n 的整数序列 a，现在需要求 f(a_1)+f(a_1+a_2)+\dots+f(a_1,a_2,\dots,a_n) 的值。
数据范围： 1\le n\le 2\times10^5,1\le a_i\le 10^9。

题目解析

对于任意一个区间，如果左端点不变，右端点右移，那么这个区间内数字的最大公约数显然不增，这个区间的长度（也就是 r-l+1） 增大。所以确定一个左端点之后，如果保证左端点 l 为定值，那么满足 \gcd(a_l,a_{l+1},\dots,a_r)= r-l+1 最多只有 1 个。
我们可以用 ST 表求出满足 \gcd(a_l,a_{l+1},\dots,a_r)= r-l+1 的所以有序整数对 (l,r)。

然后不难发现一个引理：如果 l,r 满足 \gcd(a_l,a_{l+1},\dots,a_r)= r-l+1，那么我们只需要在 l,r 之间任意修改一个数字就可以满足题目的条件了。
这样就成了线段覆盖问题，只需要按左端点从小到大排序（其实求出来的时候就是按照左端点从小大的所以不需要排序），然后每个区间尽量选择最右边的点即可。

核心代码：

int gcd(int x,int y){ if(!x) return y; if(!y) return x; return gcd(y,x%y); }
int n,ln,a[maxn],st[20][maxn];
int l[maxn],r[maxn],cnt,nowgcd,nowr,ans[maxn],las,lasans;
int main(){
    n=read(); ln=log2(n); int i,j; for(i=1;i<=n;i++) a[i]=read(),st[0][i]=a[i];
    for(j=1;j<=ln;j++) for(i=1;i<=n;i++) if(i+(1<<j)-1<=n) st[j][i]=gcd(st[j-1][i],st[j-1][i+(1<<(j-1))]);
    for(i=1;i<=n;i++){
        nowgcd=a[i]; nowr=i; if(a[i]==1){ l[++cnt]=i; r[cnt]=i; continue; }
        for(j=ln;j>=0;j--) if(nowr+(1<<j)<=n&&gcd(nowgcd,st[j][nowr+1])>=nowr+(1<<j)-i+1)
            nowgcd=gcd(nowgcd,st[j][nowr+1]),nowr=nowr+(1<<j);
        if(nowgcd==nowr-i+1) l[++cnt]=i,r[cnt]=nowr;
    }
    for(i=1;i<=cnt;i++) if(l[i]>las){ ans[r[i]]=++lasans; las=mmax(las,r[i]); }
    for(i=1;i<=n;i++) ans[i]=mmax(ans[i],ans[i-1]),print(ans[i]),pc(' '); return 0;
}