Codeforces 1632 D. New Year Concert —

Codeforces 1632 D. New Year Concert —— 线段树+尺取

本文主要是介绍Codeforces 1632 D. New Year Concert —— 线段树+尺取，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一个长度为n的数组，你要修改其中的某些值使得任意的l,r, $g c d (a [l], a [l + 1] . . . a [r]) = = r - l + 1$ 的情况不存在。
对于所有的前缀都做一遍。

题解：

这道题…解题思路在题目中提到了：枚举所有右端点，然后检查左端点。
具体是检查什么，怎么检查。那么我们第一个可以发现的是答案一定是不会减小的，因为你要能让i这个位置满足，必然要让前面的位置也满足。怎么改很重要，如果改不好的话，那是否前面检查过的位置在后面还需要检查一遍呢？
其实很简单，如果当前位置要改，直接改成与当前所有数都互质的数即可。那么后面的位置检查到这里的时候，gcd一定会变成1，也就不用再往前面检查了。
如果我们枚举右端点，然后再枚举左端点检查是否gcd和长度相等的话，时间复杂度是O(n^2)的，怎么办？
可以发现这样一个规律：左端点往左移动的时候，长度一定增加，gcd一定不增加，也就是你右端点往右走的同时，gcd和长度相等的位置一定不会往左移动。
考虑尺取，对于如何快速地求出gcd的问题，使用线段树即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],gcd[N*4];
void build(int l,int r,int root){if(l==r){gcd[root]=a[l];return ;}int mid=l+r>>1;build(l,mid,root<<1);build(mid+1,r,root<<1|1);gcd[root]=__gcd(gcd[root<<1],gcd[root<<1|1]);
}
int query(int l,int r,int root,int ql,int qr){if(l>=ql&&r<=qr)return gcd[root];int ans=0,mid=l+r>>1;if(mid>=ql)ans=query(l,mid,root<<1,ql,qr);if(mid<qr)ans=__gcd(ans,query(mid+1,r,root<<1|1,ql,qr));return ans;
}
int main()
{int n,pos=0,ans=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);for(int i=1;i<=n;i++){if(a[i]==1)ans++,pos=i;else{int g=query(1,n,1,pos+1,i);while(g<i-pos){pos++;g=query(1,n,1,pos+1,i);}if(g==i-pos)ans++,pos=i;}printf("%d%c",ans," \n"[i==n]);}return 0;
}