专栏文章

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

ddeepthinker
P8539题解参与者 6已保存评论 5

文章操作

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

当前评论
5 条
当前快照
1 份
快照标识符
@mio4yoa1
此快照首次捕获于
2025/12/02 13:26
3 个月前
此快照最后确认于
2025/12/02 13:26
3 个月前
查看原文

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

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

题目大意

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

算法思路

观察

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

数学推导

对于位置 xx 要至少被选中 kk 次，需要满足：
  1. 对于前面的要求：ss 必须 ≥ 前 x−1x-1 次操作后的最大值 prexpre_x
  2. 在区间里的要求：对于 j∈[x+1,x+k−1]j \in [x+1, x+k-1]，需要满足： s+(j−x)×v>ajs + (j - x) \times v > a_j

线段树优化

使用线段树维护 aj−j×va_j - j \times v 的最大值，可以快速计算：
s>aj−(j−x)×vs > a_j - (j - x) \times v
对于所有 j∈[x+1,x+k−1]j \in [x+1, x+k-1]，需要： s>max⁡j=x+1x+k−1{aj−(j−x)×v}+1s > \max_{j=x+1}^{x+k-1} \{a_j - (j - x) \times v\} + 1

代码

CPP
#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;
}
完结撒花~~

评论

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

正在加载评论...