专栏文章

唐

__jxy
P11753题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7tg2w
此快照首次捕获于
2025/12/04 00:22
3 个月前
此快照最后确认于
2025/12/04 00:22
3 个月前
查看原文
因为只有一个半小时打，赛时 T5 又被卡常卡了 5050 分钟，所以这题没写完 qwq。
这是个大水题，因为如果 ii 关于区间 [l,r][l,r] 是好的，那么 ii 一定在 ll 和 rr 之间。而且显然区间 gcd⁡\gcd 是有单调性的，所以考虑二分。每次二分出以 ii 为右端点的区间 gcd⁡\gcd 为 hih_i 的最小左端点和以 ii 为左端点的区间 gcd⁡\gcd 为 hih_i 的最大右端点，两个下标减一减加一就是最终答案，而且区间 gcd⁡\gcd 是可以用 st 表预处理的。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...