题解：AT_abc388_g [ABC388G] Simultaneous Kagamimochi 2

2huk · 2025-01-12 18:58:55 · 题解

显然二分。考虑 check k 是否合法。

根据 E 的思路，显然要把 [l, l+k-1] 这些积木按顺序依次摞到 [r-k+1,r] 上面。我们要判断是否合法。

注意到如果第 i 块积木将要摞在上面，那么它下面的积木应该是 r-l+1-k+i。也就是说，k 合法等价于对于所有 i \in [l, l+k-1] 都满足 2a_i \le a_{r-l+1-k+i}。

预处理 p_i 表示 [i+1,n] 中第一个 \ge 2a_i 的位置，不存在为无穷大。那么上面那个条件可以等价地写成 p_i \le r-l+1-k+i，即 p_i-i \le r-l+1-k。

判断「对于所有 i \in [l, l+k-1] 是否都满足 p_i-i \le r-l+1-k」，可以求区间 [l,l+k-1] 的 p_i-i 的最大值。静态 RMQ 用 ST 表即可解决。

int n, a[N], p[N];
int st[N][20];

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

bool chk(int l, int r, int k) {
    return query(l, l + k - 1) <= r - l + 1 - k;
}

void Luogu_UID_748509() {
    cin >> n;

    for (int i = 1; i <= n; ++ i ) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++ i ) {
        p[i] = lower_bound(a + i + 1, a + n + 1, a[i] * 2) - a;
        if (p[i] == n + 1) p[i] = 1e9;
        // cout << i << " : " << p[i] << '\n';
        p[i] -= i;
        st[i][0] = p[i];
    }

    for (int j = 1; j < 20; ++ j )
        for (int i = 1; i + (1 << j - 1) <= n; ++ i )
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);

    int q;
    cin >> q;
    while (q -- ) {
        int l, r;
        cin >> l >> r;

        int lo = 1, hi = (r - l + 1) / 2, res = 0;
        while (lo <= hi) {
            int mid = lo + hi >> 1;
            if (chk(l, r, mid)) res = mid, lo = mid + 1;
            else hi = mid - 1;
        }

        cout << res << '\n';
    }
}