[Medium-Hard] CF2025G Variable Damage

xiezheyuan2025/1/27约 1909 字大约 10 分钟

简要题意

有一个游戏，这个游戏中有若干个英雄和若干个道具，每个英雄存在生命值，每一个道具存在耐久度，每个英雄最多持有一件道具。

游戏开始时，你需要给每一个英雄分配一个道具（可能存在英雄没有道具或道具没有英雄），然后销毁未被分配的道具。

接下来有若干轮，每轮令每个英雄的生命值和每个道具的耐久度减去 $(a+b)^{-1}$ ，其中 $a$ 表示存活的英雄数量， $b$ 表示存在的道具数量，当英雄生命值小于等于 $0$ 时即死亡，当道具耐久度小于等于 $0$ 时，或持有它的英雄死亡时即销毁。当没有英雄存活时，游戏结束。你需要最大化游戏的轮数。

初始时，没有英雄和道具，有 $n$ 次操作，每次操作可以增加一个指定生命值的英雄，或增加一个指定耐久度的道具，然后你需要输出若此时进行一次游戏，游戏的轮数最大值。

$1\leq n\leq 3\times 10^5$ 。

思路

为什么我觉得这道题不套路？是我见的套路太少了吗？

Part 1

先不考虑道具和动态插入，考虑下面这个问题：给定 $n$ 个英雄的生命值 $a_1,\cdots,a_n$ ，输出游戏轮数。直接考虑每个英雄受到的伤害比较复杂，不妨将所有英雄看成一个整体，那么相当于每轮对这个整体造成 $1$ 点伤害，故总游戏轮数就是 $\sum a_i$ 。

然后我们加入道具，不过假设道具已经配好对了，具体来说第 $i$ 个道具分配给第 $i$ 个英雄，耐久度为 $b_i$ 。那么道具其实可以看成 $\min(a_i,b_i)$ 生命值的英雄，转换成了前面的问题。

所以现在的问题是需要将 $a,b$ 排序，使得 $\sum \min(a_i,b_i)$ 最大。可以证明，只需要让 $a,b$ 均降序排序即可，为了使本部分内容流畅，我将证明放在了文末。

Part 2

不过 $\sum\min(a_i,b_i))$ 这个形式似乎很难动态维护。这里我们需要另外一个 trick，将英雄和道具合并到一起，全部降序排序，然后对于一个道具，如果前面存在英雄没有匹配，那么需要匹配前面的一个英雄，贡献是自己的耐久度；对于一个英雄，如果前面存在道具没有匹配，那么需要匹配前面的一个道具，贡献为自己的生命值。

这个形式似乎有一点前途，不妨将“存在英雄没有匹配”改为“前面的英雄数量多于道具的数量”，不难证明这是等价的。

于是我们不妨改为维护每一个位置前（可以包括自己或者不包括自己，这是实现的细节）的英雄数量与道具数量之差，则英雄若产生贡献需要 $<0$ （如果在前面你选择的是包括自己，那么应该是 $\leq 0$ ），道具则需要 $>0$ （同理）。

将所有询问离线后对每一个数值离散化（出现多次的数，分配不同的编号），这样就变成了后缀加上或减去 $1$ ，查询全局 $>0$ 或 $<0$ 的元素的权值之和。

分块，有一个简单的 $O(n\sqrt{n\log n})$ 的做法，无法通过本题。

Part 3

我们的 $\log$ 来自于查询时整块的二分查找（修改时散块重构时排序的 $\log$ 很容易用归并技巧来消去），如果我们可以直接开桶记录每个数的在序列中出现的位置的权值和，就可以去掉这个 $\log$ 了，由于每次只是 $\pm1$ ，所以可以用桶，不过这样就需要 $O(n\sqrt{n})$ 的空间。

这时观察我们分块的修改操作的特殊性质，每个后缀只会修改一次，故每个块的值域其实最多为 $[T+1,T+\sqrt{n}]$ ，只需要在散块重构时将 $T$ 设定为块中最小值减 $1$ ，就可以让值域变为 $[1,\sqrt{n}]$ ，这样只需要 $O(n)$ 的空间了。

时间复杂度 $O(n\sqrt{n})$ 空间复杂度 $O(n)$ 可以通过本题。

代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;

using i64 = long long;
const int N = 3e5 + 5, SQRTN = 555;
int m;

struct option{
    int op, v, id, pos;
} a[N];

struct blocking{
    int bl[N], br[N], bel[N], blk;
    int a[N], tag[N], val[N];
    i64 sumt[SQRTN][SQRTN];

    void init(){
        blk = sqrt(m);
        for(int i=1;i<=m/blk;i++) bl[i] = (i - 1) * blk + 1, br[i] = i * blk;
        br[m / blk] = m;
        for(int i=1;i<=m/blk;i++){
            for(int j=bl[i];j<=br[i];j++) bel[j] = i;
        }
    }

    void maintain(int k){
        int tmp = (*min_element(a + bl[k], a + br[k] + 1)) - 1;
        tag[k] += tmp;
        for(int i=1;i<=br[k]-bl[k]+1;i++)  sumt[k][i] = 0;
        for(int i=bl[k];i<=br[k];i++) sumt[k][a[i] -= tmp] += val[i];
        for(int i=1;i<=br[k]-bl[k]+1;i++) sumt[k][i] += sumt[k][i - 1];
    }

    void update(int p, int v){
        if(p > m) return;
        for(int i=p;i<=br[bel[p]];i++) a[i] += v;
        maintain(bel[p]);
        for(int i=bel[p]+1;i<=bel[m];i++) tag[i] += v;
    }

    i64 query(bool op){ // op = 0: < 0, op = 1: > 0
        i64 ans = 0;
        for(int i=1;i<=bel[m];i++){
            int bd = -tag[i] + (op ? 1 : -1);
            if(!op) ans += sumt[i][max(min(bd, br[i] - bl[i] + 1), 0)];
            else ans += sumt[i][br[i] - bl[i] + 1] - sumt[i][min(max(bd - 1, 0), br[i] - bl[i] + 1)];
        }
        return ans;
    }

    void add(int p, int v){ val[p] = v,  maintain(bel[p]); }
} heroes, artifacts;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> m;
    for(int i=1;i<=m;i++) cin >> a[i].op >> a[i].v, a[i].id = i;
    sort(a + 1, a + m + 1, [](auto x, auto y){ return x.v > y.v; });
    for(int i=1;i<=m;i++) a[i].pos = i;
    sort(a + 1, a + m + 1, [](auto x, auto y){ return x.id < y.id; });
    heroes.init(), artifacts.init(); i64 all = 0;
    for(int i=1;i<=m;i++){
        int op = a[i].op, v = a[i].v, pos = a[i].pos, tag = op == 1 ? 1 : -1;
        (op == 1 ? heroes : artifacts).add(pos, v);
        if(op == 1) all += v;
        heroes.update(pos + 1, tag), artifacts.update(pos + 1, tag);
        cout << heroes.query(0) + artifacts.query(1) + all << '\n';
    }
    return 0;
}

// Written by xiezheyuan

附：对于文中贪心的证明

所以现在的问题是需要将 $a,b$ 排序，使得 $\sum \min(a_i,b_i)$ 最大。

这个形式很像 exchange argument，所以可以考虑邻项交换模型，假如交换 $(i,j)$ ，若 $i$ 更优，则：

\min(a_i,b_i)+\min(a_j,b_j)\geq \min(a_i,b_j)+\min(a_j,b_i)

首先若 $a_i=a_j$ 或 $b_i=b_j$ ，则可以随意交换，故下面不考虑。

变形得：

\min(a_i+a_j,b_i+b_j,a_i+b_j,a_j+b_i)\geq \min(a_i+a_j,b_i+b_j,a_i+b_i,a_j+b_j)

由于 $\min$ 中四个和大小关系难以确定，而两边都有 $a_i+a_j,b_i+b_j$ ，为了保证恒成立，则有：

\min(a_i+b_j,a_j+b_i)\geq \min(a_i+b_i,a_j+b_j)

考虑在何时这个式子恒成立。我们下面证明，最小值不会同时为括号中的第一个值或第二个值。

不妨反证法，假如均取到第一个值（第二个值是类似的），则有 $a_i+b_j\leq a_j+b_i,a_i+b_i\leq a_j+b_j$ ，稍作变形得到 $a_i-a_j\leq b_i-b_j,a_i-a_j\leq b_j-b_i$ ，由于 $b_i\neq b_j$ ，故得证。

然后当 $a_i>a_j,b_i>b_j$ ，此时 $a_i+b_j>a_j+b_j$ ， $a_j+b_i<a_i+b_i$ ，讨论若左边最小值为 $a_i+b_j$ ，则不等式成立，若最小值为 $a_j+b_i$ ，又有 $a_j+b_i>a_j+b_j$ ，所以不等式恒定成立，故换成 $a_i>a_j,b_i>b_j$ 一定是不劣的，这就是正文中的贪心策略。