[CF1398E] Two Types of Spells

Description

动态维护一个技能集合，技能分为两种，普通技能和超级技能。所有技能会被按照一个排列执行，如果技能 (i) 被执行时它的前一个技能是普通技能，那么会产生 (w_i) 的贡献；如果是超级技能则会产生 (2w_i) 的贡献。每次添加或删除技能后，求当前技能集合的最大贡献。

Solution

考虑维护三个技能集合：setNormal 表示普通技能集合，setHigh 表示当前所有技能中，贡献较高的技能的集合，setLow 为 setHigh 的补集。

在任意时刻，我们控制 setHigh 的大小为当前超级技能的总个数，那么 sum(*)+sum(setHigh) 基本就是答案，但需要做一点修正。

考虑如果我们希望将所有的超级技能翻倍，但这时一定有一个超级技能是不能被翻倍的（显然我们会选择最小的那一个）。

考虑如果我们希望翻倍的技能中有一个不是超级技能，那么这时这些技能被同时翻倍是可以满足的。

因此，我们从上面的近似答案中，减去当前 setHigh 集合的最小值，再加上当前 setNormal 集合的最大值，就是答案。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

#define dbg(y, x) ;

int n, countMagic, ans;
set<int> setHigh, setLow, setNormal;

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    while (n--)
    {
        int type, value;
        cin >> type >> value;
        ans += value;
        if (value > 0)
        {
            if (type == 0)
                setNormal.insert(value);
            if (type == 1)
                countMagic++;
            if (setHigh.size() && value >= *setHigh.begin())
                setHigh.insert(value), ans += value;
            else
                setLow.insert(value);
        }
        else
        {
            value *= -1;
            if (type == 0)
                setNormal.erase(value);
            if (type == 1)
                countMagic--;
            if (setLow.find(value) != setLow.end())
                setLow.erase(value);
            else
                setHigh.erase(value), ans -= value;
        }
        while (setHigh.size() > countMagic)
        {
            ans -= *setHigh.begin();
            setLow.insert(*setHigh.begin());
            setHigh.erase(*setHigh.begin());
        }
        while (setHigh.size() < countMagic)
        {
            ans += *setLow.rbegin();
            setHigh.insert(*setLow.rbegin());
            setLow.erase(*setLow.rbegin());
        }
        int tans = ans;
        if (setHigh.size())
        {
            tans -= *setHigh.begin();
            if (setNormal.size())
                tans += *setNormal.rbegin();
            if (tans > ans)
                tans = ans;
        }
        cout << tans << endl;
        dbg("lowSize", setLow.size());
        dbg("highSize", setHigh.size());
    }
}