Codeforces Round #769 (Div. 2)D,E

传送门
题目大意：
一个长为 N ( 1 ≤ N ≤ 2 × 1 0 5 ) N(1leq Nleq2times 10^5) N(1≤N≤2×105)的序列 A A A，对于 [ l , r ] [l,r] [l,r]，如果 g c d ( A l , A l + 1 , . . . , A r ) = r − l + 1 gcd(A_{l},A_{l+1},...,A_{r})=r-l+1 gcd(Al​,Al+1​,...,Ar​)=r−l+1，称这一段不好，每次操作可以将数列上任意一个位置上的数字替换为任意一个正整数。对序列的每个前缀，求出最少操作多少次可以使该前缀上没有不好的段。

思路：
因为可以修改为任意的正整数，所以我们只要将 A i A_{i} Ai​修改为一个很大的素数，那么所有包含 i i i的不好的段都会变好。

再考虑从每个左端点 l l l开始的段，显然随着 r r r的增加，本段的 g c d gcd gcd不增，而 r − l + 1 r-l+1 r−l+1会逐渐增大，也就是 g c d gcd gcd与 r − l + 1 r-l+1 r−l+1最多有一个交点，也就是对于每个左端点，最多有 1 1 1个不好的段，不好的段总数最多为 N N N。

我们可以用 S T ST ST表来求区间 g c d gcd gcd，然后枚举每个左端点二分求出所有不好的段。

接下来就是求最少修改多少个点可以使所有不好的段消失，我们可以对求出的所有不好的段按右端点排序，按右端点从小到大枚举，如果该段仍然存在，就修改该段右端点上的元素，同时所有包含该点的不好的段也都消失。最后对表示每个点是否被修改的数组求一个前缀和即为答案。

代码：

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
//#define int LL
#define endl 'n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#pragma warning(disable :4996)
const double eps = 1e-8;
const LL mod = 1000000007;
const LL MOD = 998244353;
const int maxn = 200010;

int N, A[maxn], ST[maxn][30];
vectorseg;
int ans[maxn];

bool cmp(const PII& a, const PII& b)
{
	if (a.second == b.second)
		return a.first < b.first;
	return a.second < b.second;
}

int gcd(int a, int b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);
}

void GCD_init(int n)
{
	for (int i = 0; i < n; i++)
		ST[i][0] = A[i];
	for (int j = 1; (1 << j) <= n; j++)
	{
		for (int i = 0; i + (1 << j) - 1 < n; i++)
			ST[i][j] = gcd(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
	}
}

int GCD(int l, int r)//[l,r)
{
	if (l >= r)
		return 0;
	int k = floor(log2(r - l));

	return gcd(ST[l][k], ST[r - (1 << k)][k]);
}

void solve()
{
	GCD_init(N + 1);
	for (int i = 1; i <= N; i++)
	{
		int lo = i, hi = N + 1;
		while (hi - lo > 1)
		{
			int mid = (lo + hi) / 2;
			if (GCD(i, mid + 1) >= mid + 1 - i)
				lo = mid;
			else
				hi = mid;
		}
		if (GCD(i, lo + 1) == lo + 1 - i)
			seg.push_back(PII(i, lo));
	}
	sort(seg.begin(), seg.end(), cmp);
	int lst = 0;
	for (auto& s : seg)
	{
		int l = s.first, r = s.second;
		if (l <= lst)
			continue;
		lst = r;
		ans[r] = 1;
	}
	for (int i = 1; i <= N; i++)
	{
		ans[i] += ans[i - 1];
		cout << ans[i] << ' ';
	}
	cout << endl;
}

int main()
{
	IOS;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> A[i];
	solve();

	return 0;
}

题目大意：

思路：

代码：

一会儿再补