LG6619-[省选联考 2020 A/B 卷] 冰火战士题解

虽然说这题题意还是比较好懂的，但我代码调了好久。

题意

选取一个最合适的温度$k$,使得
$$
\large{\min \left( \sum_{i \in \mathrm{ice},x_i \le k} y_i, \sum_{i \in \mathrm{fire},x_i \ge k} y_i\right)}
$$
的值最大。如果有多个$k$能使价值最大，则选最大的$k$。

分析

首先由题意我们知道，对于$\mathrm{ice}$来说，我们得到的是一个递增序列。对于$\mathrm{fire}$来说，我们得到的是一个递减序列。把两个序列合起来，我们可以得到一个单峰曲线。
那么我们很容易想到我们用二分选取最优温度。

然后呢？

我就在这里卡死了，万能的题解给出了一个不错的解法 –>
我们找到$\mathrm{ice}$的能量$f_i$小于$\mathrm{fire}$的能量$g_i$的最高温度$k$,那么一定有$f(k+1) \ge g(k+1)$，在这个时候我们再找到一个$k’$,使$g(k+1)=g(k)$,那么答案就是$\max(k,k’)$

很有道理，于是 开始打代码 又偷瞄了一眼题解，发现前车之鉴只能拿$60pts$，于是看到了解决方案

显而易见 我们可以用一种直接在树状数组上二分（倍增）的做法，加上吸氧即可通过本题！

为什么可以倍增呢？
如果我们现在在$p$位置，我们在树状数组上倍增的时候，跳的步长$d$递减如$2^{20},2^{19},2^{18},2^{17},2^{16} \cdots 2^0$，而我们知道，树状数组一个点上存储的是$\left[p+1,p+d\right]$上的所有信息，那么我们最不用重新算前后缀和，直接将$p+d$上点的信息加起来即可。

具体看代码实现。

AC Code

#include<iostream>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);return x*f;}
struct query{
    int opt;
    int k;
    int t,temp,power;
}req[2000005];
int n,tr[2][2000005],SUM;
int temp[2000005],tot;
//树状数组部分
int lowbit(int x){
    return x&(-x);
}
void add(int pos,int y,int whi){
    for(int i = pos;i<=tot;i+=lowbit(i)){
        tr[whi][i]+=y;
    }
}
int query(int x,int whi){
    int ans=0;
    for(int i = x;i;i-=lowbit(i)){
        ans+=tr[whi][i];
    }
    return ans;
}
//树状数组部分

int main(){
    n=read();
    for(int i = 1;i<=n;i++){
        req[i].opt=read();
        if(req[i].opt&1){
            req[i].t=read(),req[i].temp=read(),req[i].power=read();
            temp[++tot]=req[i].temp;
        }else req[i].k=read();
    }
    sort(temp+1,temp+tot+1);
    tot=unique(temp+1,temp+tot+1)-temp-1;//离散化温度
    for(int i = 1;i<=n;i++){
        if(req[i].opt&1){
            req[i].temp=lower_bound(temp+1,temp+tot+1,req[i].temp)-temp;
        }
    }//将每个点的温度改为离散化后的值
    for(int i = 1;i<=n;i++){
        if(req[i].opt&1) add(req[i].temp+req[i].t,req[i].power,req[i].t),SUM+=req[i].t*req[i].power/* 这里是为了方便后续求前后缀和 */;
        else{
            int whi = req[i].k;
            add(req[whi].temp+req[whi].t,-req[whi].power,req[whi].t),SUM-=req[whi].t*req[whi].power;
        }
        //对操作后的树进行修改
        int sum0=0,sum1=SUM,f0=0,pos0=0;
        for(int i = 20;i>=0;i--){//倍增
            int now_pos = pos0+(1<<i),now_sum0 = sum0+tr[0][now_pos],now_sum1=sum1-tr[1][now_pos];
            if(now_pos>tot)continue;
            if(now_sum0<now_sum1){
                pos0 = now_pos;
                sum0 = now_sum0,sum1 = now_sum1;
            }
        }
        f0=sum0,sum0=0,sum1 = SUM;
        //到这里算出了k的值即这里的pos0
        int f1=0,pos1=0;
        if (pos0 < tot){
            f1 = min(query(pos0+1,0),SUM-query(pos0+1,1));
            //找到g(k+1)
            for(int i = 20;i>=0;i--){
                int now_pos = pos1 + (1 << i),now_sum0 = sum0+tr[0][now_pos],now_sum1=sum1-tr[1][now_pos];
                if(now_pos>tot)continue;
                if(now_sum0<now_sum1){
                    pos1 = now_pos;
                    sum0 = now_sum0,sum1 = now_sum1;
                }else if(min(now_sum0, now_sum1) == f1){
                    pos1 = now_pos;
                    sum0 = now_sum0,sum1 = now_sum1;
                }
            }
            //把k'的位置搜出来
        }
        if(!(f0|f1))cout<<"Peace\n";
        else if(f0>f1)cout<<temp[pos0]<<" "<<(f0<<1)<<endl;
        else cout<<temp[pos1]<<" "<<(f1<<1)<<endl;
    }
    return 0;
}