CF1879F Last Man Standing

题目链接：https://codeforces.com/problemset/problem/1879/F

题意简述

有 $n$ 位英雄，每位英雄都有护甲值 $a$ 和生命值 $h$。对一次伤害值为 $x$ 的游戏，每位英雄的存活时间为 $t = \lceil a / x \rceil \cdot h$。

游戏进行无数次，伤害值从 $1$ 到无穷。某一次游戏中，存活时间最长的英雄获得等同于其单独存活的时间的分数。求每位英雄在单次游戏中获得分数的最大值。

$n, x, a \le 2 \times 10^5$。

题解（官解）

首先，显然所有 $\ge \max a$ 的伤害值等价，因此只需考虑 $1 \le x \le \max a$。

对该范围内每个 $x$，需要求出最大的两个 $t$ 以及最大的一个的下标。我们将护甲值按照 $c = \lceil a /x\rceil$ 分类，对每个 $x$ 枚举这一类别。则对相同的 $c$，即 $x\cdot(c-1) + 1 \le a \le x \cdot c$，$t$ 的相对大小即 $h$ 的相对大小。

枚举 $c$，只要能够在 $O(1)$ 时间内找到 $h$ 最大和次大的两个元素，根据调和级数的性质，即可在 $O(a\log a)$ 时间内求出最终答案——这可以通过 ST 表实现。注意合并时需要考虑两个区间内最大元素为同一个元素的情况（因为 ST 表可能有重叠）。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

using P = pair<int, int>;
void solve() {
    int n;
    cin >> n;
    vector<int> h(n), a(n);
    for (int &x : h)
        cin >> x;
    for (int &x : a)
        cin >> x;
    int m = ranges::max(a);
    auto add = [&h](P a, P b) {
        P res{-1, -1};
        if (a.first == -1 || (b.first != -1 && h[a.first] < h[b.first]))
            res.first = b.first;
        else res.first = a.first;
        for (auto i : {a.first, a.second, b.first, b.second}) {
            if (i != -1 && i != res.first &&
                (res.second == -1 || h[i] > h[res.second])) {
                res.second = i;
            }
        }
        return res;
    };
    vector st(19, vector<P>());
    st[0] = vector<P>(m + 1, {-1, -1});
    for (int i = 0; i < n; i++) {
        st[0][a[i]] = add(st[0][a[i]], {i, -1});
    }
    for (int b = 1; (1 << b) <= m + 1; b++) {
        st[b] = vector<P>(m + 1 + 1 - (1 << b));
        for (int i = 0; i + (1 << b) <= m + 1; i++) {
            st[b][i] = add(st[b - 1][i], st[b - 1][i + (1 << (b - 1))]);
        }
    }
    auto query = [&](int l, int r) {
        r = min(r, m);
        int len = 32 - 1 - countl_zero((unsigned)(r - l + 1));
        return add(st[len][l], st[len][r + 1 - (1 << len)]);
    };
    vector<i64> ans(n, 0);
    for (i64 x = 1; x <= m; x++) {
        i64 mx = 0, smx = 0;
        int idx = -1;
        for (i64 c = 1; c * x <= m + x - 1; c++) {
            auto [idx1, idx2] = query(x * (c - 1) + 1, x * c);
            for (int i : {idx1, idx2}) {
                if (i == -1) continue;
                auto t = c * h[i];
                if (t > mx) {
                    smx = mx;
                    mx = t, idx = i;
                } else if (t > smx) smx = t;
            }
        }
        if (~idx) ans[idx] = max(ans[idx], mx - smx);
    }
    for (i64 x : ans)
        cout << x << " ";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}