codeforces-Ed93-E

codeforces-Ed93-E

八月 16, 2020

E. Two Types of Spells

题意

n个法术槽 n<2e5

第i次会向法术槽种添加或删除一个法术(所有法术伤害不同)

tp=1是lighting 使出造成di点伤害并会使下一个法术伤害翻倍

tp=0是fire 使出造成di点伤害

每次 添加或删除一个法术后

求出某种出招顺序使得用当前存在的法术打出最大伤害

题解

首先考虑在某时刻 法术槽有k个lighting 和m个fire

最大伤害= 所有法术的伤害+ 其中最大的k个法术的伤害

因为lighting法术的buff 相当于能在使用k个法术造成伤害

于是从(k+m)个法术中选取k个伤害最大的最优

但是有个细节若k个伤害最大的法术全为lighting

那么其中伤害最小的lighting将无法被二次释放

具体的以A为ligthing B为fire

若k个最大的全为lighting：

AA….AABBBB 那么最开始的A不能被释放两次

所以A(A…AB)B…BB 括号里的法术被释放两次

若k个最大的有至少一个为fire(B)

那么总有多余的A(不在前k大的法术中)可以使B释放两次 其余的A可以连续释放添加buff

所以无论如何最小的A放在最开始 两种情况都能构造出最大解

于是问题变成了：

1.向集合(Allspell和Light)中添加或删除法术

2.查询集合(Light)中最小伤害的法术

3.查询集合(Allspell)中k个伤害最大的法术

上述要求可以用权值线段树实现

/————————————-/

我们首先将n次向集合中添加或删除法术 离散化 作为建立权值线段树的预处理

然后第i次我们会向权值线段树(Allspell)中插入/删除一个所有操作中伤害第di大的法术

完成插入删除操作后求出最大伤害

对于之前讨论如何使用法术最优

可以先求出Light集合中的最小值minLight,将它从Allspell中删去

再求Allspell中求出k个伤害最大的法术

最后将minLight放回Light

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
const double PI=acos(-1);
/*
*/
vector<ll>arr;
int tp[Max],op[Max];
ll d[Max];
struct Node{ll sum,cnt;};
///cnt记录该结点下有几数
///sum记录该结点中所有数的和
struct Tree{
    Node tree[Max<<2];
    void push_up(int now){
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
        tree[now].cnt=tree[now<<1].cnt+tree[now<<1|1].cnt;
    }
    void updata(int pos,int val,int l,int r,int node){
        //cout<<l<<" "<<r<<endl;
        if(l==r){
            tree[node].cnt+=val;
            tree[node].sum+=val*arr[l];
            ///由于所有法术伤害不同其实这里不用×val
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)updata(pos,val,l,mid,node<<1);
        else updata(pos,val,mid+1,r,node<<1|1);
        push_up(node);
    }
    ll querySum(int k,int l,int r,int node){
        if(k<=0)return 0;
        if(tree[node].cnt<=k)return tree[node].sum;
        if(l==r)return arr[l];
        int mid=(l+r)>>1;
        ll ans=0;
        if(tree[node<<1|1].cnt>=k)ans=querySum(k,mid+1,r,node<<1|1);
        else {
            k-=tree[node<<1|1].cnt;
            ///这里相当于右结点有m个那从左右结点中取第k大就是在左结点找第k-m大的数
            ans=tree[node<<1|1].sum+querySum(k,l,mid,node<<1);
        }
        return ans;
    }
    ///由于我们不知道每次添加/删除后权值线段树的最小值所以每次必须询问最小值
    ///此函数返回最小值在离散化数组中的下标
    int queryMin(int l,int r,int node){
        if(l==r)return l;
        int mid=(l+r)>>1;
        if(tree[node<<1].cnt)return queryMin(l,mid,node<<1);
        else return queryMin(mid+1,r,node<<1|1);
    }
}Allspell,Light;
int main() {
    //Turnoff;
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>tp[i]>>d[i];
        arr.push_back(abs(d[i]));
        op[i]=(d[i]>0);//第i次操作是删除还是添加
    }
    ///离散化
    sort(arr.begin(),arr.end());
    arr.erase(unique(arr.begin(),arr.end()),arr.end());
    int len=arr.size(),num=0;
    for(int i=0;i<n;i++)d[i]=lower_bound(arr.begin(),arr.end(),abs(d[i]))-arr.begin();
    //将d[i]从原来的伤害重定义为所有伤害中第几大
    for(int i=0;i<n;i++){
        //cout<<"ok"<<endl;
        if(op[i]){
            if(tp[i]==0)Allspell.updata(d[i],1,0,len-1,1);
            else{
                num++;//记录有多少个Light法术
                Allspell.updata(d[i],1,0,len-1,1);
                Light.updata(d[i],1,0,len-1,1);
            }
        }
        else{
            if(tp[i]==0)Allspell.updata(d[i],-1,0,len-1,1);
            else{
                num--;
                Allspell.updata(d[i],-1,0,len-1,1);
                Light.updata(d[i],-1,0,len-1,1);
            }
        }
        //cout<<"ok"<<endl;
        ll ans=Allspell.tree[1].sum;
        if(num){
            int minLight=Light.queryMin(0,len-1,1);
            Allspell.updata(minLight,-1,0,len-1,1);
            //cout<<ans<<" "<< Allspell.querySum(num,0,len-1,1)<<endl;
            ans+=Allspell.querySum(num,0,len-1,1);
            Allspell.updata(minLight,1,0,len-1,1);
        }
        cout<<ans<<endl;
    }
}