Educational Codeforces Round 93 (Rated for Div. 2) E. Two Types of Spells

题意：两种技能，火焰只造成伤害，闪电造成伤害并使下一个技能伤害翻倍，不断学习/遗忘技能，求每次学习或遗忘后新技能集合能造成的最大伤害

贪心，让闪电安排伤害最高的技能（无关闪电还是火焰），同时为了最大化，把第一个技能安排成最小的闪电（因为它不能被加倍）

题意变成了求前K大，求最小

安排两个权值线段树，第一个维护所有技能，操作前先删了最小的闪电，完了再加回去；第二个只维护闪电，用来求最小的闪电

复杂度O(nlogn)

常规不开longlong见祖宗

#include<bits/stdc++.h>

using namespace std;

inline int rd(){
	int ret=0,f=1;char c;
	while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
	while(isdigit(c))ret=ret*10+c-'0',c=getchar();
	return ret*f;
}
#define pc putchar
#define space() pc(' ')
#define nextline() pc('
')
void pot(int x){if(!x)return;pot(x/10);pc('0'+x%10);}
void out(int x){if(!x)pc('0');if(x<0)pc('-'),x=-x;pot(x);}

const int MAXN=200005;

#define ls (cur<<1)
#define rs (cur<<1|1)

typedef long long ll;

int tp[MAXN],d[MAXN];
int sav[MAXN],num;
ll ans[MAXN];
int n;
struct Tree{
    ll a[MAXN<<3];
    ll sum[MAXN<<3];
    void update(int x,int val,int l,int r,int cur){
        if(l==r){
            a[cur]+=val;
            sum[cur]+=val*sav[l];
            return ;
        }
        int mid=(l+r)>>1;
        if(x<=mid)update(x,val,l,mid,ls);
        else update(x,val,mid+1,r,rs);
        a[cur]=a[ls]+a[rs];
        sum[cur]=sum[ls]+sum[rs];
    }
    ll query(int k,int l,int r,int cur){
        if(k<=0)return 0;
        if(a[cur]<=k)return sum[cur];
        if(l==r)return k*sav[l];
        int mid=(l+r)>>1;
        ll ans=0;
        if(a[rs]>=k){
            ans=query(k,mid+1,r,rs);
        }else{
            k-=a[rs];
            ans=sum[rs]+query(k,l,mid,ls);
        }
        return ans;
    }
    ll query_min(int l,int r,int cur){
        if(l==r)return l;
        int mid=(l+r)>>1;
        if(a[ls])return query_min(l,mid,ls);
        else return query_min(mid+1,r,rs);
    }
}T,T2;
int main(){
    n=rd();
    for(int i=1;i<=n;i++){
        tp[i]=rd();d[i]=rd();
        sav[i]=abs(d[i]);
    }
    sort(sav+1,sav+1+n);
    num=unique(sav+1,sav+1+n)-sav-1;
    for(int i=1;i<=n;i++){
        int f=(d[i]<0);
        d[i]=lower_bound(sav+1,sav+1+num,abs(d[i]))-sav;
        if(f)d[i]=-d[i];
    }
    int nn=0;
    for(int i=1;i<=n;i++){
        if(d[i]>0){
            if(tp[i]==0){//
                T.update(d[i],1,1,num,1);
            }else{
                nn++;
                T.update(d[i],1,1,num,1);
                T2.update(d[i],1,1,num,1);
            }
        }else{
            d[i]=-d[i];
            if(tp[i]==0){
                T.update(d[i],-1,1,num,1);
            }else{
                nn--;
                T.update(d[i],-1,1,num,1);
                T2.update(d[i],-1,1,num,1);
            }
        }
        ans[i]=T.sum[1];
        if(!nn)continue;
        int mi=T2.query_min(1,num,1);
        T.update(mi,-1,1,num,1);
        ans[i]+=T.query(nn,1,num,1);
        T.update(mi,1,1,num,1);
    }
    for(int i=1;i<=n;i++){
    	printf("%lld
",ans[i]);
    }
    return 0;
}