[数据结构与算法]D. New Year Concert && 线段树

【传送门】Problem - D - Codeforces

大概题意就是，一个数组a，每一个区间gcd(区间左起l，右终于r)，当这个区间最大公约数 == r - l + 1 时，这个区间是boring 的，可以修改区间某值，使这个区间不boring， 求使这个数组任意区间都是不boring要修改几个值，然后按照到某位置要最少修改几个值输出。

解：

首先很容易想明白，如果一个区间是boring?的， 那么我们可以修改某个数为任意的大质数，要使数量最少，贪心下，然要修改的值尽量后。然后每个修改后的值就相当于一面墙

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
typedef long long ll;
const int N = 5*1e5+1000;
 
int n,m;
ll a[N],b[N];
struct  Tree{
	int l,r;
	ll gcd;
}t[4*N];
 
ll GCD(ll x,ll y)
{
	return y == 0 ? x : GCD(y,x%y); 
} 
 
void build(int p,int l,int r){
	t[p].l = l, t[p].r = r; 
	if(l == r){
		t[p].gcd = a[l];
		return;
	} 	
	int mid = (l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].gcd = GCD(t[p*2].gcd,t[p*2+1].gcd);
}
 
ll ask(int p,int l,int r){
	if(l <= t[p].l && r >= t[p].r){
		return t[p].gcd;
	}
	int mid = (t[p].l + t[p].r)>>1;
	ll ans1 = 0, ans2 = 0;
	if(l <= mid){
		ans1 = ask(p*2, l, r);
	} 
	if(r > mid){
		ans2 = ask(p*2+1, l, r);	
	}
	if(ans1 && ans2) return GCD(ans1, ans2);
	else{
		if(ans1 == 0) return ans2;
		else return ans1;
	}
	
}
 
int main(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%lld",&a[i]);
	}
	build(1,1,n);

	int ans = 0;
    int maxr = -1;
    int pt = 1;
    for(int i = 1; i <= n; i ++){
        while(pt < i && ask(1, pt, i) < i - pt + 1) ++pt;
        int d = ask(1, pt, i);
        if(ask(1, pt, i) == i - pt + 1){
            if(pt > maxr){
                ++ans;
                maxr = i;
            }
        }
        cout << ans << " ";
    }   
	return 0;
}