CodeForces - 1398E Two Types of Spells

传送门：CodeForces - 1398E

思路分析

设$cnt$为闪电法术的数量，那么显然给$cnt$个法术享受加倍是最优的，也就是总法术的前$cnt$大加倍
但是第一个闪电法术不能够加倍，用一个线段树维护总法术，求前$cnt$大的和就行了

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a, b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror = 0;

    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if (p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }

    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }

    template<class T>
    inline bool read(T &x) {
        bool sign = 0;
        char ch = nc();
        x = 0;
        for (; blank(ch); ch = nc());
        if (IOerror)return false;
        if (ch == '-')sign = 1, ch = nc();
        for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
        if (sign)x = -x;
        return true;
    }

    template<class T, class... U>
    bool read(T &h, U &... t) {
        return read(h) && read(t...);
    }

#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 2e5+10;
#define int long long 

vector<int>v;
struct question{
    int op,x;
}q[N];

struct node{
    int num,sum;
}tree[N<<2];

#define ls x<<1
#define rs x<<1|1

void pp(int x){
    tree[x].sum = tree[ls].sum+tree[rs].sum;
    tree[x].num = tree[ls].num+tree[rs].num;
}

void modify(int x,int l,int r,int val,int k){
    if(l==r){
        tree[x].sum+=(k*v[l]);
        tree[x].num+=k;
        return ;
    }
    int mid = l+r>>1;
    if(val<=mid) modify(ls,l,mid,val,k);
    else modify(rs,mid+1,r,val,k);
    pp(x);
}

int query(int x,int l,int r,int k){
    if(k<=0) return 0;
    if(l==r) return v[l]*k;
    if(tree[x].num<=k) return tree[x].sum;
    int mid = l+r>>1;
    int rnum = tree[rs].num;
    int ans = 0;
    if(k<=rnum) ans = query(rs,mid+1,r,k);
    else ans = tree[rs].sum + query(ls,l,mid,k-tree[rs].num);
    return ans;
}

signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    read(n);
    int sum = 0;
    int cnt = 0;
    set<int>B;
    v.pb(0);
    for(int i=1;i<=n;i++) {
        read(q[i].op,q[i].x);
        if(q[i].x>=0) v.pb(q[i].x);
    }
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    int tot=sz(v);
    for(int i=1;i<=n;i++){
        int x = abs(q[i].x);
        x = lower_bound(all(v),x)-v.begin();
        if(q[i].x>0) q[i].x=x;
        else q[i].x=-x;
    }

    for(int i=1;i<=n;i++){
        if(q[i].op==0){
            if(q[i].x>0){
                sum+=v[q[i].x];
                modify(1,1,tot,q[i].x,1);
            }else{
                q[i].x=-q[i].x;
                sum-=v[q[i].x];
                modify(1,1,tot,q[i].x,-1);
            }
        }else{
            if(q[i].x>0){
                sum+=v[q[i].x];
                cnt++;
                B.insert(q[i].x);
                modify(1,1,tot,q[i].x,1);
            }else{
                q[i].x=-q[i].x;
                sum-=v[q[i].x];
                B.erase(B.find(q[i].x));
                modify(1,1,tot,q[i].x,-1);
                cnt--;
            }
        }
        int mi = B.size()?*B.begin():0;
        if(mi) modify(1,1,tot,mi,-1);
        printf("%lld\n",sum + query(1,1,tot,cnt));
        if(mi) modify(1,1,tot,mi,1);
    }



    return 0;
}

&nbsp;