Codeforces Round 769 (Div. 2) D. New Year Concert

题面看这里

给你一个只含正整数的数组 \(a\)，你可以任意修改其中的元素为任意正整数，问你对于 \(a\) 的每个前缀数组\((a_1,a_1a_2,a_1a_2a_3\dots)\)，至少需要修改多少个元素，才能满足：该前缀数组中不存在任何一个子区间 \(a_l,a_{l+1}\dots a_{r-1},a_r\)，满足 \(\gcd(a_l,a_{l+1}\dots a_{r-1},a_r)=r-l+1\)，即每个子区间的区间 \(\gcd\) 都不等于区间长度。

\((1\leq n\leq 2e5,~1\leq a_i\leq1e9)\)

首先考虑最暴力的算法，从左到右，对于每个位置 \(i\)，我们对他前面的每一个位置 \(j(1\leq j\leq i)\) 都判断一下，看下 \(a_j\) 到 \(a_i\) 的区间 \(\gcd\) 是否等于区间长度，如果每个都不等，则不需要修改；否则，至少要修改一个数，修改谁呢？修改为啥呢？设我们要修改的数为 \(a_k\)，注意到可以修改为任意正整数，显然我们只需要将其修改成一个特别大的质数，就可以在保证 \([1,i]\) 区间合法性的同时，让处在后面的区间 \([k+1,n]\) 中的每个位置 \(i'\) 只需判断 \([k+1,i']\) 即可，所以为了保证修改次数为最小，\(k\) 一定要取最大值，因此 \(k=i\)，只需修改 \(a_i\) 即可。

区间 \(\gcd\) 可以用 st表 或者 线段树 \(n\log n\) 预处理出来，然后每次查询区间 \(\gcd\) 的时间复杂度是 \(\log n\) 总复杂度 \(O(n^2\log n)\)，伪代码如下：

int last=0,ans=0;	//last记录的是上一次修改的位置,j只需要遍历[last+1,i]即可,小优化
for(int i=1;i<=n;i++){
    bool flag=true;
    for(int j=i;j>last;j--){
        if(query(j,i)==i-j+1){
            flag=false;
            break;
        }
    }
    if(!flag) ans++,last=i;
    cout << ans << " ";
}

接下来考虑优化，注意到重点是对于每一个非法的区间，我们都要修改其右端点的数，显然，对于一个左端点 \(l_x\)，最多只能有一个右端点跟它构成非法区间。（左端点固定的区间 \(\gcd\) 是非递增的，而区间长度又是递增的，假如这个非法区间为 \([l_x,r_x]\)，那么 \(r_x\) 之后的区间 \(\gcd\) 只会不变或者更小，而区间长度一定会变大，所以一定不相等）

因此，对于每个位置 \(i\)，我们需要找到以它为左端点的非法区间的右端点，记为 \(v_i\)，如果不存在则令 \(v_i=0\)。那么我们就可以 \(O(n)\) 求出答案：

long long nex=inf;	//在多个非法区间中选出最小的右端点,即为下一次要修改的位置
for(int i=1;i<=n;i++){
    if(v[i]){
        nex=min(nex,v[i]);
    }
    if(i==nex){
        ans++;
        nex=inf;
    }
    cout << ans << " ";
}

现在问题转化为了找到每个非法区间，通过上面的分析，发现 \(\gcd([l_x,r_x])\geq r_x-l_x+1\) 这个式子具有单调性，如果 \([l_x,r_x]\) 满足该式子，则 \([l_x,r_y(l_x\leq r_y\leq r_x)]\) 也一定满足，因此我们可以固定 \(l_x\)，然后二分查找最大的 \(r_x\) 满足 \(\gcd([l_x,r_x])\geq r_x-l_x+1\)，最后再判断一下是否相等，相等就找到了一个非法区间。时间复杂度 \(O(n\log n\log n)\))。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=LLONG_MAX/10;
constexpr int maxn=2e5+6;
long long n,m,k,ans,_=1,a[maxn],v[maxn];
long long f[maxn][22];
long long lg[maxn];
long long gcd(long long a,long long b){
	if(!a||!b) return a+b;
	while((a%=b)&&(b%=a)) ;
	return a+b;
}
void init(){
	lg[0]=-1;
	for(int i=1;i<=n;i++){
		f[i][0]=a[i],lg[i]=lg[i>>1]+1;
	}
	lg[0]=0;
	for(int j=1;j<=lg[n];j++){
		for(int i=1;i+(1<<j)<n+2;i++){
			f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
long long query(int l,int r){
	int len=lg[r-l+1];
	return gcd(f[l][len],f[r-(1<<len)+1][len]);
}
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	init();
	for(int i=1;i<=n;i++){
		int l=i,r=n,mid,rr;
		while(l<=r){
			mid=l+r>>1;
			long long d=query(i,mid);
			if(d>=mid-i+1){
				rr=mid;
				l=mid+1;
			}
			else {
				r=mid-1;
			}
		}
		if(query(i,rr)==rr-i+1){
			v[i]=rr;
		}
	}
	long long nex=inf;
	for(int i=1;i<=n;i++){
		if(v[i]){
			nex=min(nex,v[i]);
		}
		if(i==nex){
			ans++;
			nex=inf;
		}
		cout << ans << " ";
	}
}