自动搬运

查看原文

来自洛谷，原作者为

	jiangxinyang2012 我常常追忆过去。

搬运于2025-08-24 23:09:59，当前版本为作者最后更新于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;
}