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

#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;
}