唐

jiangxinyang2012 · 2025-02-19 21:41:52 · 题解

因为只有一个半小时打，赛时 T5 又被卡常卡了 50 分钟，所以这题没写完 qwq。

这是个大水题，因为如果 i 关于区间 [l,r] 是好的，那么 i 一定在 l 和 r 之间。而且显然区间 \gcd 是有单调性的，所以考虑二分。每次二分出以 i 为右端点的区间 \gcd 为 h_i 的最小左端点和以 i 为左端点的区间 \gcd 为 h_i 的最大右端点，两个下标减一减加一就是最终答案，而且区间 \gcd 是可以用 st 表预处理的。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 1000005;
const int INF = 0x3f3f3f3f;
int a[N], dp[N][32];
void st_init(int n) {
    for (int i = 1; i <= n; i++) dp[i][0] = a[i];
    int p = __lg(n);
    for (int k = 1; k <= p; k++) {
        for (int s = 1; s + (1 << k) <= n + 1; s++) {
            dp[s][k] = __gcd(dp[s][k - 1], dp[s + (1 << (k - 1))][k - 1]);
        }
    }
}
int st(int l, int r) {
    int k = __lg(r - l + 1);
    int x = __gcd(dp[l][k], dp[r - (1 << k) + 1][k]);
    return x;
}
int L[N], R[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    st_init(n);
    for (int i = 1; i <= n; i++) {
        int l = 1, r = i, res = i;
        while (l <= r) {
            int mid = l + r >> 1;
            if (st(mid, i) == a[i]) {
                r = mid - 1;
                res = mid;
            } else {
                l = mid + 1;
            }
        }
        L[i] = res;
    }
    for (int i = 1; i <= n; i++) {
        int l = i, r = n, res = i;
        while (l <= r) {
            int mid = l + r >> 1;
            if (st(i, mid) == a[i]) {
                l = mid + 1;
                res = mid;
            } else {
                r = mid - 1;
            }
        }
        R[i] = res;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", R[i] - L[i] + 1);
    }
    printf("\n");
    return 0;
}