「题解」「联合省选 2020 B」冰火战士 icefire

2020年6月25日 0 联合省选

题目链接：联合省选 2020 B D1T3/Luogu P6619/LibreOJ 3299。

注：本题与 联合省选 2020 A D1T1 一模一样，所以发了两篇一样的博客。

题目

题目描述

一场比赛即将开始。

每位战士有两个属性：温度和能量，有两派战士：冰系战士的技能会对周围造成降温冰冻伤害，因而要求场地温度不低于他的自身温度才能参赛；火系战士的技能会对周围造成升温灼烧伤害，因而要求场地温度不高于他的自身温度才能参赛。

当场地温度确定时，双方能够参赛的战士分别排成一队。冰系战士按自身温度从低到高排序，火系战士按自身温度从高到低排序，温度相同时能量大的战士排在前面。首先，双方的第一位战士之间展开战斗，两位战士消耗相同的能量，能量少的战士将耗尽能量退出比赛，而能量有剩余的战士将继续和对方的下一位战士战斗（能量都耗尽则双方下一位战士之间展开战斗）。如此循环，直至某方战士队列为空，比赛结束。

你需要寻找最佳场地温度：使冰火双方消耗总能量最高的温度的最高值。

现在，比赛还处于报名阶段，目前还没有任何战士报名，接下来你将不断地收到报名信息和撤回信息。其中，报名信息包含报名战士的派系和两个属性，撤回信息包含要撤回的报名信息的序号。每当报名情况发生变化（即收到一条信息）时，你需要立即报出当前局面下的最佳场地温度，以及该场地温度下双方消耗的总能量之和是多少。若当前局面下无论何种温度都无法开展比赛（某一方没有战士能参赛），则只要输出 Peace。

数据范围

$10\%$ 的数据：$Q\leq 100,x\leq 10^3$。

另有 $20\%$ 的数据：$Q\leq 10^4,x\leq 5000$，不存在撤回信息，且输入的 $x$ 按顺序不降。

$60\%$ 的数据（包含上述 $20\%$，下同）：$Q\leq 2\times 10^5,x\leq 2\times 10^5$。

$90\%$ 的数据：$Q\leq 2\times 10^6,x\leq 2\times 10^6$。

$100\%$ 的数据：$Q\leq 2\times 10^6,x\leq 2\times 10^9$，所有 $y$ 之和不超过 $2\times 10^9$，保证不存在 $t,x,y$ 完全相同的两个战士。

时空限制

题目编号时间限制空间限制
联合省选 2020 B D1T3$3\text{s}$$512\text{MiB}$

题解

本题有部分分做法，在介绍解法之前，我们可以先得出答案
$$\texttt{ans}=2\min _ {x _ 0}\{\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i+\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i\}$$

解法 A（暴力）

对于 $10\%$ 的数据：$Q\leq 100,x\leq 10^3$。

那么我们不妨开一个以时间下标的数组，每个地方用 vector 存放信息，记录当前时间点的战士信息，这需要我们预先处理出报名信息有效的时间范围，再一个一个赋值、插入。

查询时每个节点上的战士信息先按照温度排序，最后枚举温度 $x$，用前缀和快速算出答案即可。

这种做法的复杂度为 $\Theta(Q^2+Q\max\{x\}\log _ 2Q)$，期望得分为 $10$ 分。

解法 B（还是暴力）

另有 $20\%$ 的数据：$Q\leq 10^4,x\leq 5000$，不存在撤回信息，且输入的 $x$ 按顺序不降。

我们可以把解法 A 的暴力优化一下。

那么我们不妨开一个以时间下标的数组，每个地方用 vector 存放信息，记录当前时间点的战士信息，这需要我们预先处理出报名信息有效的时间范围，再一个一个赋值、插入。

因为没有撤回消息，报名第 $i$ 条报名信息的有效时间一定为 $[i,Q]$，这样我们就不用一个一个插入了，每条报名信息直接插到生效的时间节点上，查询时做个前缀和一样的东西即可。

查询时每个节点上的战士信息先按照温度排序，最后枚举温度 $x$，用前缀和快速算出答案即可。

因为输入的 $x$ 按顺序不降。所以不用排序。

这种做法的复杂度为 $\Theta(Q+Q\max\{x\})$，期望得分为 $20$ 分，加上解法 A 的 $10$ 分，总计能拿到 $30$ 分。

解法 C（常用技巧）

$60\%$ 的数据（包含上述 $20\%$，下同）：$Q\leq 2\times 10^5,x\leq 2\times 10^5$。

没有了特殊性质，我们只能从暴力的解法 A 出发，对算法进行优化。

开一个以时间下标的数组，每个地方用 vector 存放信息，记录当前时间点的战士信息，这需要我们预先处理出报名信息有效的时间范围，再一个一个赋值、插入。

仔细思考可以发现一个一个赋值、插入信息实在是太慢了，我们不妨把插入报名信息这个过程高度抽象，视作是对以时间为下标的序列的区间修改。

这使得我们想到了线段树，我们可以通过线段树把统计报名信息的这一部分优化到 $\Theta(Q\log _ 2Q)$。

另外，这种把时间抽象为序列的做法被称作 线段树分治。

查询时每个节点上的战士信息先按照温度排序，最后枚举温度 $x$，用前缀和快速算出答案即可。

枚举是查询这一步的瓶颈所在，我们需要找到一种方法，快速确定使得答案最大的温度 $x$。

假设我们确定了当前比赛选手的信息，

解法 D（数学做法）

$60\%$ 的数据（包含上述 $20\%$，下同）：$Q\leq 2\times 10^5,x\leq 2\times 10^5$。

首先仔细观察答案
$$\texttt{ans}=2\min _ {x _ 0}\{\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i+\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i\}$$

我们可以把括号里的那个式子拿出来观察
$$\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i+\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i$$

不妨把它切成两个部分
$$f(x _ 0)=\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i$$

$$g(x _ 0)=\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i$$

不难发现，随着 $x _ 0$ 的增大，$f(x _ 0)$ 单调不降，$g(x _ 0)$ 单调不增。

分析答案表达式可知
$$\texttt{ans}=2\min _ {x _ 0}\{f(x _ 0)+g(x _ 0)\}$$

这是一个下凸函数。

但是由于本题对输出的位置存在限制，所以三分完了还要套一个二分。

我们可以三分求最大值，时间复杂度为 $\Theta(Q\log^2 _ 2Q+2Q\log _ 2Q\log _ 3\max\{x\})$，期望得分 $60$ 分。

解法 E（正解）

令 $X(T)=F(T)-I(T)$，显然 $X(T)$ 是个不增函数。如果我们能二分出 $X$ 的零点，就能优化到一个 $\log$。

考虑在线段树上维护，每个节点维护一个 $V$ 的最大值（代码中用的是 $\texttt{ice}$）（也就是这段区间左端点的 $V$ 值）。然后能尽量往右走就往右走。

我们还要找到最大的下标。分类讨论即可。时间复杂度 $\Theta(Q\log _ 2Q)$。

但由于常数原因，这种做法在洛谷上过不了，其他 OJ 能过。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXQ=2000000+5;

struct Node{
    int val,id;
    inline Node(reg int val=0,reg int id=0):val(val),id(id){
        return;
    }
    inline bool operator<(const Node& a)const{
        return val<a.val;
    }
};

static char wbuf[1000000];
int wp;

inline void pc(reg char x){
    if(wp>=1000000)
        fwrite(wbuf,1,1000000,stdout),wp=0;
    wbuf[wp++]=x;
    return;
}

inline void write(reg int x){
    int c[12]={0};
    if(!x)
        return pc('0'),void();
    while(x)
        c[++c[0]]=x%10,x/=10;
    while(c[0])
        pc(c[c[0]--]+'0');
    return;
}

Node V[MAXQ];

struct Message{
    int opt,t,x,y;
};

Message M[MAXQ];

namespace SegmentTree{
    #define lson ( (k) << 1 )
    #define rson ( (k) << 1 | 1 )
    struct Node{
        int L,R;
        int Max,tagM;
        int fire,tagF;
        #define L(x) unit[(x)].L
        #define R(x) unit[(x)].R
        #define Max(x) unit[(x)].Max
        #define tagM(x) unit[(x)].tagM
        #define fire(x) unit[(x)].fire
        #define tagF(x) unit[(x)].tagF
    };
    Node unit[MAXQ<<2];
    inline void Build(reg int k,reg int l,reg int r){
        L(k)=l,R(k)=r,Max(k)=tagM(k)=0;
        if(l==r)
            return;
        reg int mid=(l+r)>>1;
        Build(lson,l,mid);
        Build(rson,mid+1,r);
        return;
    }
    inline void AddI(reg int k,reg int val){
        Max(k)+=val;
        tagM(k)+=val;
        return;
    }
    inline void AddF(reg int k,reg int val){
        fire(k)+=val;
        tagF(k)+=val;
        return;
    }
    inline void pushdown(reg int k){
        if(tagM(k)){
            AddI(lson,tagM(k));
            AddI(rson,tagM(k));
            tagM(k)=0;
        }
        if(tagF(k)){
            AddF(lson,tagF(k));
            AddF(rson,tagF(k));
            tagF(k)=0;
        }
        return;
    }
    inline void UpdateI(reg int k,reg int l,reg int r,reg int val){
        if(R(k)<l||r<L(k))
            return;
        if(l<=L(k)&&R(k)<=r){
            AddI(k,val);
            return;
        }
        pushdown(k);
        UpdateI(lson,l,r,val);
        UpdateI(rson,l,r,val);
        Max(k)=Max(lson);
        return;
    }
    inline void UpdateF(reg int k,reg int l,reg int r,reg int val){
        if(R(k)<l||r<L(k))
            return;
        if(l<=L(k)&&R(k)<=r){
            AddF(k,val);
            return;
        }
        pushdown(k);
        UpdateF(lson,l,r,val);
        UpdateF(rson,l,r,val);
        fire(k)=fire(lson);
        return;
    }
    inline int findI(reg int k,reg int val){
        if(Max(k)<val)
            return 0;
        if(L(k)==R(k))
            return L(k);
        pushdown(k);
        if(Max(rson)>=val)
            return findI(rson,val);
        else
            return findI(lson,val);
    }
    inline int findF(reg int k,reg int val){
        if(fire(k)<val)
            return 0;
        if(L(k)==R(k))
            return L(k);
        pushdown(k);
        if(fire(rson)>=val)
            return findF(rson,val);
        else
            return findF(lson,val);
    }
    inline int Query(reg int k,reg int pos){
        if(L(k)==R(k))
            return Max(k);
        pushdown(k);
        reg int mid=(L(k)+R(k))>>1;
        if(pos<=mid)
            return Query(lson,pos);
        else
            return Query(rson,pos);
    }
    #undef lson
    #undef rson
}

struct TreeArray{
    int size,unit[MAXQ];
    #define lowbit(x) ( (x) & ( - (x) ) )
    inline void add(reg int ID,reg int val){
        for(reg int i=ID;i<=size;i+=lowbit(i))
            unit[i]+=val;
        return;
    }
    inline int pre(reg int ID){
        reg int res=0;
        for(reg int i=ID;i;i-=lowbit(i))
            res+=unit[i];
        return res;
    }
    inline void Init(reg int S){
        size=S;
        //memset(unit,0,sizeof(unit));
        return;
    }
    inline int suf(reg int ID){
        return pre(size)-pre(ID-1);
    }
    #undef lowbit
};

TreeArray Max,fire;

inline void output(reg int p,reg int x){
    if(!x)
        pc('P'),pc('e'),pc('a'),pc('c'),pc('e'),pc('\n');
    else
        write(V[p].val),pc(' '),write(x<<1),pc('\n');
    return;
}

int main(void){
    reg int Q=read();
    reg int cnt=0;
    for(reg int i=1;i<=Q;++i){
        M[i].opt=read();
        if(M[i].opt==1)
            M[i].t=read(),M[i].x=read(),M[i].y=read(),V[++cnt]=Node(M[i].x,i);
        else
            M[i].x=read();
    }
    sort(V+1,V+cnt+1);
    for(reg int i=1,val=1;i<=cnt;++i){
        if(V[i].val!=V[i-1].val)
            val=i;
        M[V[i].id].x=val;
    }
    Max.Init(cnt),fire.Init(cnt);
    using namespace SegmentTree;
    Build(1,1,cnt);
    reg int cnt0=0,cnt1=0;
    for(reg int i=1;i<=Q;++i){
        switch(M[i].opt){
            case 1:{
                if(M[i].t==0){
                    ++cnt0;
                    Max.add(M[i].x,M[i].y);
                    UpdateI(1,M[i].x,cnt,-M[i].y);
                }
                else{
                    ++cnt1;
                    fire.add(M[i].x,M[i].y);
                    UpdateI(1,1,M[i].x,M[i].y);
                    UpdateF(1,1,M[i].x,M[i].y);
                }
                break;
            }
            case 2:{
                reg int k=M[i].x;
                if(M[k].t==0){
                    --cnt0;
                    Max.add(M[k].x,-M[k].y);
                    UpdateI(1,M[k].x,cnt,M[k].y);
                }
                else{
                    --cnt1;
                    fire.add(M[k].x,-M[k].y);
                    UpdateI(1,1,M[k].x,-M[k].y);
                    UpdateF(1,1,M[k].x,-M[k].y);
                }
                break;
            }
        }
        if(!cnt0||!cnt1)
            pc('P'),pc('e'),pc('a'),pc('c'),pc('e'),pc('\n');
        else{
            reg int p=findI(1,0);
            if(p==cnt)
                output(p,Max.pre(cnt));
            else if(p==0)
                output(findF(1,fire.suf(1)),fire.suf(1));
            else{
                reg int val=fire.suf(p+1);
                reg int p2=findF(1,val);
                reg int ans1=min(Max.pre(p),fire.suf(p)),ans2=min(Max.pre(p2),fire.suf(p2));
                if(ans1>ans2)
                    output(p,ans1);
                else
                    output(p2,ans2);
            }
        }
    }
    fwrite(wbuf,1,wp,stdout);
    return 0;
}

Tags:

Lu-Anlai

江西赣州人

You may also like...

发表评论