题解：P12718 [Algo Beat Contest 002 E] Excellent Game

CleverSea · 2025-07-08 15:50:48 · 题解

板子题居然没什么人写题解？

题意简述

有 N 个数组，每个数组长度为 L_i，元素为 \{A_{i,1},A_{i,2},\dots,A_{i,L_i}\}。游戏进行 Q 轮，每轮操作选择恰好一个数组，将其所有元素增加 K（K 可为负）。游戏结束后，最大化所有元素中前 M 大的元素之和。

分析

首先我们要搞清楚：最优策略一定是将所有 Q 次操作施加在同一个数组上。本蒟蒻给出一个看起来不怎么严谨的证明如下：

• 若 K > 0，集中操作使一个数组的所有元素增加 Q \times K，比分散操作（多个数组各增加部分量）更可能产生更大的元素，从而提升前 M 大的和。

• 若 K < 0，集中操作使一个数组的所有元素减少 |Q \times K|，保护其他数组元素不变。相比分散操作（多个数组均减少），不变的元素更可能成为前 M 大，从而总和更大。

搞懂了这点之后，我们便可以思考使用的数据结构。我们发现题目要求支持维护值域，进行单点更新（插入/删除）和查询前 M 大的和。这不就是权值线段树的板子题吗？

由此，题目就好做了——

• 线段树节点存储区间内元素个数 cnt 和元素和 sum。

• 查询前 M 大时，从右子树（大值）开始递归。每次检查右子树中数的个数是否够，如果够，则递归右子树继续检查；如果不够，则递归左子树。

• 枚举每个数组：

  • 将当前数组的所有元素从线段树中删除（原始值）。
  • 插入操作后的值（原始值 + \text{delta}）。
  • 查询前 M 大的和，更新答案。
  • 还原线段树（删除操作值，插入原始值）。

• 记得离散化（权值线段树基操）。

至于为什么不需要主席树，是因为这里只需查询全局前 M 大，没有指定范围。

Code

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
const int T = 200000; // 最大数组数量

int N, M, Q; // 数组数、前M大、操作轮数
ll K, delta; // 每次操作增量、总增量Q*K
ll A[T << 1]; // 存储所有数组元素
int L[T]; // 每个数组的长度
int st[T]; // 每个数组在A中的起始索引
int tot = 0; // 总元素计数器
vector<ll> num; // 离散化数组

// 线段树节点结构体
struct Node {
    int l, r; // 节点管理的值域范围[l,r]
    ll cnt; // 该值域内元素个数
    ll sum; // 该值域内元素总和
} tree[T << 3];

// 获取值x在离散化数组中的位置
int getpos(ll x) {
    return lower_bound(num.begin(), num.end(), x) - num.begin();
}

// 线段树：更新父节点信息（cnt和sum）
void pushup(int u) {
    tree[u].cnt = tree[u << 1].cnt + tree[u << 1 | 1].cnt;
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
}

// 线段树：建树
void build(int u, int l, int r) {
    tree[u].l = l;
    tree[u].r = r;
    tree[u].cnt = tree[u].sum = 0; // 初始化为空树
    if (l == r) return; // 叶子节点无需继续分裂
    int mid = (l + r) >> 1;
    build(u << 1, l, mid); // 递归构建左子树
    build(u << 1 | 1, mid+1, r); // 递归构建右子树
    pushup(u); // 更新当前节点信息
}

// 线段树：单点更新
// pos: 要更新的离散化位置
// add: 增加的数量（+1插入，-1删除）
void update(int u, int pos, int add) {
    // 到达叶子节点
    if (tree[u].l == tree[u].r) {
        tree[u].cnt += add; // 更新计数
        tree[u].sum = tree[u].cnt * num[tree[u].l]; // 更新和
        return;
    }
    // 递归更新左/右子树
    int mid = (tree[u].l + tree[u].r) >> 1;
    if (pos <= mid) update(u << 1, pos, add);
    else update(u << 1 | 1, pos, add);
    pushup(u); // 更新当前节点
}

// 线段树：查询前k大元素的和
ll query(int u, int k) {
    // 边界情况处理
    if (k <= 0) return 0; // 取0个元素
    if (k >= tree[u].cnt) return tree[u].sum; // 取全部元素
    // 叶子节点特判：当k小于该值的出现次数时
    if (tree[u].l == tree[u].r) {
        return 1LL * k * num[tree[u].l]; // 取k个当前值
    }
    // 优先从右子树（大值）开始取
    int rson = u << 1 | 1;
    int lson = u << 1;
    if (tree[rson].cnt >= k) {
        // 右子树元素足够，完全在右子树取
        return query(rson, k);
    } else {
        // 右子树不足，取全部右子树+左子树补充
        return tree[rson].sum + query(lson, k - tree[rson].cnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> Q >> K;
    delta = 1LL * Q * K; // 计算总增量
    for (int i = 0; i < N; i++) {
        cin >> L[i];
        st[i] = tot; // 记录起始位置
        for (int j = 0; j < L[i]; j++) {
            cin >> A[tot];
            tot++;
        }
    }
    // 离散化处理：收集所有可能的值
    for (int i = 0; i < tot; i++) {
        num.push_back(A[i]); // 原始值
        num.push_back(A[i] + delta); // 操作后的值
    }
    // 排序并去重
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    int nsize = num.size(); // 离散化后的值域大小
    // 初始化线段树
    build(1, 0, nsize - 1);
    // 将所有原始值插入线段树
    for (int i = 0; i < tot; i++) {
        int pos = getpos(A[i]);
        update(1, pos, 1);
    }
    ll ans = -1e18; // 初始化为极小值
    // 枚举每个数组作为操作对象
    for (int i = 0; i < N; i++) {
        // 将当前数组替换为操作后的值
        for (int j = st[i]; j < st[i] + L[i]; j++) {
            ll a = A[j];
            int lastpos = getpos(a);
            int newpos = getpos(a + delta);
            update(1, lastpos, -1); // 删除原始值
            update(1, newpos, 1); // 插入操作后值
        }
        // 查询当前状态下的前M大和
        ll cur_ans = query(1, M);
        if (cur_ans > ans) {
            ans = cur_ans; // 更新最大值
        }
        // 还原线段树状态
        for (int j = st[i]; j < st[i] + L[i]; j++) {
            ll a = A[j];
            int lastpos = getpos(a);
            int newpos = getpos(a + delta);
            update(1, newpos, -1); // 删除操作后值
            update(1, lastpos, 1); // 重新插入原始值
        }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度

令 p = \sum L_i，则：

离散化：O(p \log p)。

线段树更新和查询：O(p \log p)。

总复杂度：O(p \log p)。

番外

本蒟蒻一开始提交时忘记特判叶子结点导致 WA on #40——评测记录。