题解：P8539 「Wdoi-2」来自地上的支援

deepthinker · 2025-08-25 20:39:11 · 题解

P8539 「Wdoi-2」来自地上的支援题解

省流：线段树好题（好像可以O(n)做，但蒟蒻太菜啦）

题面传送门

题目大意

有 n 个核反应机组，第 i 个机组的初始活动强度为 A_i。依次进行 n 次操作，第 i 次操作会在前 i 个机组中选择当前活动度最高的机组（规则详见题目），并将其活动度增加 v。 现在有 m 次询问，每次询问给出 x_i, k_i，要求找到最小的非负整数 s，使得将第 x_i 个机组的初始活动度改为 s 后，该机组至少被选中 k_i 次。如果不存在这样的 s，输出 0。

算法思路

观察

因为第 x 个数必须被选中 k 次，根据题意，不难发现这 k 次选中一定是从第 x 次操作连续 k 个被选中，所以如果一个数在前面没选中，后面就更不可能了。

数学推导

对于位置 x 要至少被选中 k 次，需要满足：

1. 对于前面的要求：s 必须 ≥ 前 x-1 次操作后的最大值 pre_x
2. 在区间里的要求：对于 j \in [x+1, x+k-1]，需要满足： s + (j - x) \times v > a_j

线段树优化

使用线段树维护 a_j - j \times v 的最大值，可以快速计算：

对于所有 j \in [x+1, x+k-1]，需要：

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2000010;
int n, m, v;
int a[N];
ll pre[N], ans1, ans2;
ll tr[4 * N];//线段树

void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = a[l] - (ll)l * v;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}

ll query(int u, int l, int r, int L, int R)
{
    if (L > R)
        return -1e18;
    if (L <= l && r <= R)
        return tr[u];
    int mid = (l + r) >> 1;
    ll res = -1e18;
    if (L <= mid)
        res = max(res, query(u << 1, l, mid, L, R));
    if (R > mid)
        res = max(res, query(u << 1 | 1, mid + 1, r, L, R));
    return res;
}

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

    cin >> n >> m >> v;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);//构建线段树
    ll cur = 0;//预处理最大值
    for (int i = 1; i <= n; i++)
    {
        pre[i] = cur;
        if (a[i] > cur)
            cur = a[i];
        cur += v;
    }
    while (m--)
    {
        int x, k;
        cin >> x >> k;

        if (x + k - 1 > n)//无法选择k次
        {
            continue;
        }
        ll s = pre[x];
        if (k > 1)
        {
          // 查询区间 [x+1, x+k-1] 的最大值
            ll qval = query(1, 1, n, x + 1, x + k - 1);
            s = max(s, qval + (ll)x * v + 1);
        }
        ans1 ^= s;
        ans2 += s;//统计答案
    }
    cout << ans1 << " " << ans2;
    return 0;
}

完结撒花~~