题解：P12194 [NOISG 2025 Prelim] Snacks

yanxu_cn · 2025-07-11 17:38:48 · 题解

本题是 STL 好练习题，标签诚不欺人。

提供一个非常简单的 map 做法。

这题甚至不需要珂朵莉树（因为这题只关心值的大小而并不关心顺序），所以直接用 map 统计数目即可。容易注意到复杂度是 O(q\log n) 并且跑不满的。

然后开好 long long 即可，注意中间会有计算过程也会爆 int，爆有符号整数在谷上是不会 RE 的，只会 WA，望周知。

贴代码。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int n,q;
    cin>>n>>q;
    map<int,int>mp;
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        mp[t]++;
        ans+=t;
    }
    cout<<ans<<'\n';
    q++;
    while(--q)
    {
        int l,r,x;
        cin>>l>>r>>x;
        int cnt=0;
        auto lp=mp.lower_bound(l),rp=mp.upper_bound(r);
        for(auto tp=lp;rp!=tp;tp++)
        cnt+=tp->second,ans-=static_cast<long long>(tp->first)*tp->second;
        mp.erase(move(lp),move(rp));
        mp[x]+=cnt;
        ans+=(long long)cnt*x;
        cout<<ans<<'\n';
    }
    return 0;
}