[ABC306E] Best Performances

[ABC306E] Best Performances

题目大意：

有一个长度为 n 的序列，最开始都是 0。
有 q 个操作，改变 a[p] 为 v。并输出前 k 大的数的和。

题目分析：

• 可以维护两个 multiset。第一个 multiset s维护前 k 大的数，第二个 multiset t维护剩下的数。
• 每次操作先寻找 a[p]是否在 s 中，如果在则 ans 减去 a[p], 然后删除 a[p]。
• 在 t 加入v。接着用 t 来更新 s 和 ans。最后把 a[p] 改为 v 输出 ans。

代码：

#include <bits/stdc++.h>

using namespace std;
template <typename _T>

inline void read(_T &x)
{
    x = 0; char c; _T d = 1;
    while(c > 57 || c < 48){
        c = getchar();
        if(c == '-') d = -1;
    }
    while(c >= 48 && c <= 57){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= d;
}

const int N = 5e5 + 5;
int n, k, q;
int a[N];
long long ans;
multiset<int> s;//从小到大排序
multiset<int, greater<int> > t;//从大到小排序

void update()
{
    while(s.size() < k){
        s.insert(*t.begin());
        ans += *t.begin();
        t.erase(t.begin());
    }
    while(*t.begin() > *s.begin()){
        ans = ans + *t.begin() - *s.begin();
        t.insert(*s.begin());
        s.erase(s.begin());
        s.insert(*t.begin());
        t.erase(t.begin());
    }
}

signed main()
{
    read(n), read(k), read(q);
    for(int i = 1; i <= k; i++) s.insert(0);
    for(int i = 1; i <= n - k; i++) t.insert(0);
    while(q--)
    {
        int p, v;
        read(p), read(v);

        t.insert(v);
        if(s.find(a[p]) != s.end()){
            s.erase(s.find(a[p]));
            ans -= a[p];
        }else{
            t.erase(t.find(a[p]));
        }
        a[p] = v;
        update();

        cout << ans << "\n"; 
    }

    return 0;
}