111

2026-10-05 17:38:31
发布于：浙江
16阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q, V;
    cin >> n >> q >> V;

    vector<int> a(n + 1);
    int D = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        D = max(D, abs(a[i] - V));
    }

    // 经过至少 B 步后，一个旧值会稳定在 V 或 V-1。
    int B = 1;
    while ((1LL << B) <= D) B++;

    // near[i]：最近 B 个起点传到 i 时，能产生的最大值。
    vector<int> near(n + 1, 0);
    for (int j = 1; j <= n; j++) {
        int x = a[j];
        for (int i = j; i <= n && i < j + B; i++) {
            near[i] = max(near[i], x);
            x = (x + V) / 2;
        }
    }

    vector<long long> sum(n + 1, 0);
    vector<int> cnt(n + 1, 0), nxt(n + 2, n + 1);

    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + max(near[i], V - 1);
        cnt[i] = cnt[i - 1] + (near[i] < V);
    }

    // nxt[i]：从 i 开始，第一个满足 a[j] >= V 的位置。
    for (int i = n; i >= 1; i--) {
        nxt[i] = (a[i] >= V ? i : nxt[i + 1]);
    }

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

        // 前 B 项直接按题意计算。
        int f = a[l];
        long long ans = f;
        int stop = min(r, l + B - 1);

        for (int i = l + 1; i <= stop; i++) {
            f = max(a[i], (f + V) / 2);
            ans += f;
        }

        if (stop < r) {
            // 后半段的基础值之和。
            ans += sum[r] - sum[stop];

            // 较早的 a[h] >= V 会把部分位置的 V-1 提高到 V。
            int h = nxt[l];
            int from = max(stop + 1, h + B);
            if (from <= r) {
                ans += cnt[r] - cnt[from - 1];
            }
        }

        cout << ans << '\n';
    }
    return 0;
}
有帮助，赞一个
去预览
0/2000
这里空空如也
热门讨论
