[数据结构与算法]D. New Year Concert（cf）gcd性质 + st表 + 二分

原题链接：Problem - 1632D - Codeforces

晚上复习的时候再补全~

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

int n;
const int N = 2e5 + 10;
ll a[N];
int Log[N];
ll st[N][21];

void init(){
for (int i = 2; i <= N; ++i) //这里如果每组询问的n不一样，这里n就要换成N
    Log[i] = Log[i >> 1] + 1;//Log[i]表示log(i) stl log用多了会卡
}

void solve( ) {
    for (int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for (int j = 1; j <= 20; j++) { //这个地方的20是根据N的大小来定的(至少log2(N))
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

ll query(int l, int r) {
    int k = Log[r - l + 1];
    return __gcd(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    init();
    solve();
    int pre = 1;
    int res = 0;
    rep(i, n)
    {
        if(a[i] == 1){
            res++;
            pre = i + 1;
        }
        else{
            int l = pre, r = i;
            int flag = false;
            while(l < r)
            {
                int mid = (l + r) >> 1;
                if(query(mid, i) >= i - mid + 1){
                    r = mid;
                    if(query(mid, i) == i - mid + 1){flag = true; break;}
                }
                else l = mid + 1;
            }
            if(query(l, i) == i - l + 1) flag = true;
            if(flag) res++, pre = i + 1;
        }
        printf("%d ", res);
    }
    return 0;
}

?