题解：P12194 [NOISG 2025 Prelim] Snacks

· · 题解

题目传送门

https://www.luogu.com.cn/problem/P12194

题意简述

题目给出 n 个装有小吃的盘子，每个盘子的小吃有初始美味值 a[i] 需要处理 q 个查询，每个查询包含三个参数 l[j],r[j],x[j] ，执行两步操作：

  1. 吃掉所有美味值在 范围内的小吃；

  2. 将被吃掉的小吃全部替换为美味值为 x[j] 的新小吃。要求输出初始状态下所有小吃的美味值总和，以及每个查询处理后的总和。

题目分析

核心矛盾与暴力解法的局限性 若采用暴力解法（每次查询遍历整个数组，检查每个元素是否在 [l[j],r[j]] 范围内并更新），时间复杂度为 O(qn)。由于 n 和 q 均可达 2×105 ，O(qn) 会达到 4×1010 次操作，远超时间限制，因此必须寻找更高效的解法。

关键观察

题目中的修改仅与 “数值本身” 相关，与 “数值所在的位置” 无关。例如，无论美味值为 v 的小吃在哪个盘子里，只要它在 [l[j],r[j]] 范围内，就会被替换为 x[j]。因此，我们无需维护每个位置的具体数值，只需维护 “每个数值出现的次数”，即可通过 “数值 × 次数” 计算其对总和的贡献。 数据结构选择 需要一种支持以下操作的数据结构：


    快速查询所有在 [l,r] 范围内的数值；
    快速获取每个数值的出现次数；
    快速删除某个数值（当次数归零时）；
    快速更新某个数值的出现次数（新增或累加）。

std::map 恰好满足这些需求

std::map 按键（数值）升序排列，支持通过 lower_bound(l) 快速找到第一个大于等于 l 的键，后续可遍历至小于等于 r 的键；每个键（数值）对应的值（次数）可直接访问，更新和查询均为 O(logk)（k 为当前数值种类数）； 支持高效的插入、删除操作，同样为 O(logk)。

整体时间复杂度为 O((n+q)log(n+q))，处理 2×105 规模的数据是没有什么问题的。


#include <iostream>
#include <map>
using namespace std;

int main() {
    // 关闭同步加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // map<美味值, 出现次数>，键有序
    map<int, long long> cnt;
    // 总和用 long long 避免溢出（1e9 * 2e5 = 2e14 > int 上限）
    long long sum = 0;

    // 初始化：统计每个美味值的次数并计算初始总和
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        cnt[a]++;          // 累加次数
        sum += 1LL * a;    // 1LL 强制转换为 long long，防止数据溢出
    }

    // 输出初始总和
    cout << sum << '\n';

    // 处理 q 个查询
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;

        long long add = 0;  // 记录当前查询中需要转移到 x 的总次数
        // 找到第一个 >= l 的美味值
        auto it = cnt.lower_bound(l);

        // 遍历所有 <= r 的美味值
        while (it != cnt.end() && it->first <= r) {
            auto next_it = next(it);  // 保存下一个迭代器，防止 erase 后失效
            long long c = it->second; // 当前美味值的出现次数

            // 更新总和：移除旧值贡献，添加新值贡献
            sum -= 1LL * it->first * c;
            sum += 1LL * x * c;

            add += c;          // 累加次数到 add，后续统一更新 x 的次数
            cnt.erase(it);     // 删除当前美味值的记录
            it = next_it;      // 迭代器后移
        }

        // 将 add 次添加到 x 的出现次数中
        if (add > 0) {
            cnt[x] += add;
        }

        // 输出当前查询后的总和
        cout << sum << '\n';
    }

    return 0;
}

审核大大求过