解题思路

可以肯定的是对于每一个lightning法术，一定要加在最大攻击上。但我们发现所加的spell肯定要有一个是fire，否则会浪费一个spell，于是我们将最大的fire单独处理，将它从平衡树上先删掉，然后计算答案，再加回去。记录最大fire可以用map+priority_queue水过。
最后我们用平衡树维护最大值即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int siz[400005],ch[400005][2],val[400005],rnd[400005];
long long sum[400005];
struct dam{
    int op,sum;
}d[200005];
int tot=0;
int new_node(int a,int b){
    tot++;
    siz[tot]=1,val[tot]=a,rnd[tot]=rand(),sum[tot]=a;
    return tot;
}
void update(int now){
    siz[now]=siz[ch[now][0]]+siz[ch[now][1]]+1;
    sum[now]=sum[ch[now][0]]+sum[ch[now][1]]+val[now];
}
void split(int now,int goal,int &x,int &y){
    if(!now){
        x=y=0;
        return ;
    }
    if(val[now]>=goal)x=now,split(ch[now][1],goal,ch[now][1],y);
    else y=now,split(ch[now][0],goal,x,ch[now][0]);
    update(now);
};
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(rnd[x]>rnd[y]){
        ch[x][1]=merge(ch[x][1],y);
        update(x);
        return x;
    }else{
        ch[y][0]=merge(x,ch[y][0]);
        update(y);
        return y;
    }
}
long long search(int now,int x){
    long long ans=0;
    while(now){
        if(x>siz[ch[now][0]]+1){
            x-=siz[ch[now][0]]+1;
            ans+=sum[ch[now][0]]+val[now];
            now=ch[now][1];
        }else if(x==siz[ch[now][0]]+1){
            ans+=sum[ch[now][0]]+val[now];
            return ans;
        }else{
            now=ch[now][0];
        }
    }
}
map<int,int> mp;
priority_queue<int,vector<int>,less<int> >q;
int main(){
    cin>>n;
    int maxn=0;
    for(int i=1;i<=n;i++){
        cin>>d[i].op>>d[i].sum;
    }
    int ji=0;
    long long ans=0;
    int root=0;
    for(int i=1;i<=n;i++){
        int x=0,y=0,z=0;
        
        if(d[i].op==1){
            if(d[i].sum<0){
                ji--;
                ans+=d[i].sum;
                split(root,-d[i].sum,x,y);
                split(x,-d[i].sum+1,x,z);
                root=merge(x,y);
            }else{
                ji++;
                
                ans+=d[i].sum;
                split(root,d[i].sum,x,y);
                root=merge(merge(x,new_node(d[i].sum,1)),y);
            }
        }else{
            if(d[i].sum<0){
                ans+=d[i].sum;
                split(root,-d[i].sum,x,y);
                split(x,-d[i].sum+1,x,z);
                root=merge(x,y);
            }
            else{
                ans+=d[i].sum;
                split(root,d[i].sum,x,y);
                root=merge(merge(x,new_node(d[i].sum,0)),y);
            }
        }
        x=y=z=0; 
        if(d[i].op==0){
            if(d[i].sum>0){
                mp[d[i].sum]++;
                q.push(d[i].sum);
            }else{
                mp[-d[i].sum]--;
                while(mp[q.top()]==0&&!q.empty()){
                    q.pop();
                }
            }
        }
        if(q.empty())maxn=0;
        else{
            maxn=q.top();
            split(root,maxn,x,y);
            split(x,maxn+1,x,z);
            root=merge(x,y);
        }
        if(ji>1)cout<<ans+maxn+search(root,ji-1)<<endl;
        else if(ji==1)cout<<ans+maxn<<endl;
        else cout<<ans<<endl;
        split(root,maxn,x,y);
        root=merge(merge(x,new_node(maxn,0)),y);
    }
    return 0;
} 

本文链接：http://kaispace.com.cn/index.php/archives/694/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者