题意翻译

你在玩一种纸牌游戏。

牌有两种，一种是普通牌，使用它可以得到它的得分；另一种是加倍牌，使用它不但可以得到它的得分，还可以让排在它后面的牌的得分 $\times 2$。

一组牌的使用顺序可以任意，其得分为每一张牌的得分之和。

现在有两种操作，每一次操作形如 opt d。

其中，$opt$ 代表牌的类型($1$ 为加倍牌，$0$ 为普通牌)。

而 $d$ 的正负代表操作类型，若 $d > 0$ ，代表你抽到了一张得分为 $d$ 的牌；反之，代表你丢弃了一张得分为 $|d|$ 的牌(丢弃纸牌不会得分)。

请回答每次操作后可能得到的最大得分。

输入格式

第一行一个整数 $n$ ，表示总操作次数。

之后 $n$ 行，每行两个整数 $opt$ , $d$ ，意义同上。

保证不会同时有两张 $d$ 相同的纸牌

输出格式

输出 $n$ 行，每行一个整数，表示该操作后可能得到的最大得分。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围和约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^9 \leq d \leq 10^9$，$opt ∈ \lbrack 0 , 1 \rbrack$。

分析

$\text{set}$ 练手题。

先说一个众所周知的事实，$\text{Codeforces}$ 的 $\text{Div 2} \text{D , E}$ 如果要支持插入删除一般都是 $\text{set}$ ~~因为别的真的没得考了……~~

现在回到这道题上。对于这道题，我们先考虑一下不带修的时候怎么做。

设 $k$ 为加倍牌的数量，有一个显然的想法就是将 $d$ 最大的 $k$ 张牌加倍。

但需要特判最大的 $k$ 张牌都是加倍牌的情况。对此，我们需要从不加倍的牌中找一个最大的替换掉加倍牌中最小的。

之后考虑如何带修。我们需要维护的东西有：加倍牌的数目，牌的类型与价值。

对此，我们可以开两个 $\text{set}$ ，一个维护前 $k$ 大，另一个维护剩下的牌。

剩下的就是细节问题了。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

ll n;
set<PLL> big , small;
ll smb , sma , smk , k;

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    read(n);
    ll now = 0;
    rep(i , 1 , n){
        ll opt , d;
        read(opt) , read(d);
        if(d > 0){
            now += opt;
            if(small.empty() || d >= small.rbegin()->fi){
                big.insert(MP(d , opt));
                smb += d;
                if(opt == 1) smk += 1;
            }
            else{
                small.insert(MP(d , opt));
                sma += d;
            }
        }
        else{
            now -= opt , d = -d;
            if(big.count(MP(d , opt))){
                big.erase(big.find(MP(d , opt)));
                smb -= d;
                if(opt == 1) smk -= 1;
            }
            else{
                small.erase(small.find(MP(d , opt)));
                sma -= d;
            }
        }
        if(big.size() > now){
            small.insert(*big.begin());
            smb -= big.begin()->fi;
            sma += big.begin()->fi;
            if(big.begin()->se == 1) smk -= 1;
            big.erase(big.begin());
        }
        else if(big.size() < now){
            big.insert(*small.rbegin());
            sma -= small.rbegin()->fi;
            smb += small.rbegin()->fi;
            if(small.rbegin()->se == 1) smk += 1;
            small.erase(--small.end());
        }
        ll res = 0;
        if(smk != now || now == 0){
            res = smb * 2 + sma;
        }
        else{
            if(small.empty()){
                res = smb * 2 + sma - big.begin()->fi;
            }
            else{
                res = smb * 2 + sma - big.begin()->fi + small.rbegin()->fi;
            }
        }
        printf("%lld\n" , res);
    }

    return 0;
}