【题解】CF1398E
解题思路
可以肯定的是对于每一个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/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者