联合省选 2020 B 解题报告

D1T3 冰火战士 icefire

题目链接:联合省选 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
} // namespace SegmentTree

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;
}
Pages: 1 2 3 4 5 6