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<=0;j--) if(nowr+(1<=nowr+(1<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;
}