题解：P12194 [NOISG 2025 Prelim] Snacks

· · 题解

题目大意

有一个长度为 n 的序列。 有 q 次查询，每次查询将输入 l,r,x，你需要将值在 \left[l,r\right] 内的所有数字都变为 x。

解法

我们可以使用 STL。

在这里，我们采用 map 来记录每个值有多少数。

于是，对于每次查询，我们将范围内的元素删除，再将 x 和对应的数量加入 map。

时间复杂度

很明显，每次修改不会增加数的总数，所以 map 最多只会修改 q+n 次，时间复杂度为 O((q+n)\log{n})，可以通过本题

代码

#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 5;
const int Mod = 1e9 + 7;
using namespace std;
int n, q;
map<int, int> mp;
signed main()
{
    int sum = 0;
    cin >> n >> q;
    while (n--)
    {
        int x;
        cin >> x;
        mp[x]++;
        sum += x;
    }
    cout << sum << endl;
    while (q--)
    {
        int l, r, x;
        cin >> l >> r >> x;
        auto it = mp.lower_bound(l);
        int cnt = 0;
        while (it != mp.end() && it->first <= r)
        {
            cnt += it->second;
            sum += (x - it->first) * it->second;
            it = mp.erase(it);
        }
        mp[x] += cnt;
        cout << sum << endl;
    }
    return 0;
}