（原文作者：Botao Yuan，由 GPT-5.4 Thinking 翻译）

题目分析

我们要求对于 $N$ 次询问，移除 $a_i$ 个草垛所需的最小花费。为了移除草垛，我们可以雇佣奶牛。第 $i$ 头奶牛有属性 $(s_i, p_i, c_i)$，表示如果当前草垛堆中有 $h$ 个草垛，我们可以花费 $c_i$ 移除

$$\min(s_i, \max(0, h - p_i + 1))$$

个草垛。

现在考虑一个最优（或者接近最优）的雇佣顺序应当是什么样的。显然，我们通常应该尽量雇佣那些 $s_i / c_i$ 更大的奶牛（前提是当前草垛数量满足 $p_i > h$）。把使这个比值最大的奶牛称为“最佳效率奶牛”。注意，每当我们处在 $p_i - 1$ 这个值时，最佳效率奶牛都可能发生变化。把所有形如 $p_i - 1$ 的值称为特殊值。

问题在于 $p_i$ 带来的限制：当 $h - p_i + 1 < s_i$ 时，一头奶牛虽然仍然花费 $c_i$，但实际移除的草垛数会少于 $s_i$。这意味着，在特殊值附近，最优策略会依赖于精确的余数，因此不能总是贪心地不断选择最佳效率奶牛直到清空所有草垛。

另一方面，如果我们离某个特殊值足够远，那么就应当反复选择最佳效率奶牛，直到到达某个需要考虑余数的阈值。事实证明，相对于当前考虑的特殊值，这个阈值是 $S^2$，其中 $S$ 是所有 $s_i$ 的最大值。

关键结论

对于 $d \ge S^2$，最优代价满足

$$f(d) = f(d - s^*) + c^*,$$

其中 $(s^*, c^*)$ 是最佳效率奶牛，也就是使 $s_i / c_i$ 最大的那头。这里，$f(x)$ 表示：相对于当前特殊值的上方，多出 $x$ 个草垛时的最小移除代价；并且只考虑满足 $p_i - 1$ 不大于当前特殊值的奶牛。

证明

考虑某个 $d \ge S^2$ 的最优解。

如果它第一步就使用了最佳效率奶牛，那么显然有

$$f(d) = c^* + f(d - s^*).$$

现在假设在前 $s^*$ 次雇佣中，最佳效率奶牛至少出现过一次，并且总共移除了 $s^*$ 个草垛。那么我们可以交换奶牛的使用顺序，使得最佳效率奶牛先被使用。因为每头奶牛移除的草垛数都不变，所以交换后 $f(d)$ 不会变化。于是仍然得到

$$f(d) = c^* + f(d - s^*).$$

否则，假设这个解在前 $s^*$ 次雇佣中完全没有使用最佳效率奶牛。设它雇佣了一串奶牛，分别移除了 $s_{i_1}, s_{i_2}, \ldots, s_{i_t}$ 个草垛，花费分别为 $c_{i_1}, \ldots, c_{i_t}$。由于每个 $s_{i_j} \le S$，并且它们的总和至少为 $d \ge S^2 \ge S \cdot s^*$，所以有 $t \ge s^*$。

只看前 $s^* + 1$ 个前缀和

$$0, s_{i_1}, s_{i_1} + s_{i_2}, \ldots$$

对 $s^*$ 取模后的结果。根据抽屉原理，其中必有两个前缀和模 $s^*$ 同余，因此在前 $s^*$ 次雇佣中，存在一个连续子段，恰好移除了 $k \cdot s^*$ 个草垛，其中 $k \ge 1$，总花费记为 $C_{\text{sub}}$。

由于 $(s^*, c^*)$ 是最佳效率奶牛，所以对任意奶牛 $i$ 都有

$$\frac{s_i}{c_i} \le \frac{s^*}{c^*},$$

也就是

$$c_i \ge \frac{s_i \cdot c^*}{s^*}.$$

把这个不等式对子段中的所有奶牛求和，可以得到

$$C_{\text{sub}} \ge \frac{(k \cdot s^*) \cdot c^*}{s^*} = k \cdot c^*.$$

因此，用 $k$ 头最佳效率奶牛替换这段连续子段，在移除草垛数相同的前提下，总代价至多为 $k \cdot c^* \le C_{\text{sub}}$。替换之后，最佳效率奶牛就会在前 $s^*$ 次雇佣中出现，且总花费不增，于是就归约到了前一种情况。因此，

$$f(d) = c^* + f(d - s^*).$$

所以，对于所有 $d \ge S^2$，都有

$$f(d) = c^* + f(d - s^*),$$

也就是说，只需要显式计算 $O(S^2)$ 个 DP 状态。

你可能会注意到，这也和 Frobenius/Coin 问题有一定相似性。

部分解法：$O(MS^3)$

我们按 $p_i$ 从小到大处理奶牛，按 $a_i$ 从小到大处理询问。同时，对于每个可能的 $s_i$，维护一头当前最优的奶牛，也就是 $s_i / c_i$ 最大的那头。每当遇到一个新的 $p_i$，就计算一个大小为 $S^2$ 的 DP 表，其中 $DP_j$ 表示当草垛数量为 $p_i - 1 + j$ 时的答案。

为了重新计算这个 DP 表，首先可以直接查询上一张 DP 表来得到初值。也就是说，对每个 $j$，把 $DP_j$ 当作对上一张 DP 表的一次询问，此时暂时不考虑新加入的奶牛。然后，对这 $S$ 头“各自 $s_i$ 下最优”的奶牛逐个做背包转移。转移方程为

$$DP_j = \min\left(DP_j,\; c + DP_{\max(0,\; j - s_i)}\right), \quad j = 0, 1, \ldots, S^2.$$

共有 $S^2$ 个状态，而每次需要进行 $S$ 轮扫描，因此复杂度是 $O(S^3)$。

处理完 $p_i$ 后，回答所有满足 $a_k < p_{i+1}$ 的询问。回答一个询问时，如果

$$a_k < p_i - 1 + S^2,$$

那么直接查表即可，答案为

$$DP_{a_k - (p_i - 1)}.$$

否则，使用最佳效率奶牛 $(s^*, c^*)$ 把 $a_k$ 降到表的范围内。令

$$q = \left\lceil \frac{a_k - (p_i - 1) - S^2 + 1}{s^*} \right\rceil,$$

则答案为

$$DP_{a_k - (p_i - 1) - q \cdot s^*} + q \cdot c^*.$$

总时间复杂度为

$$O(MS^3 + N \log N + M \log M).$$

正解：$O(MS^2)$

我们还可以进一步优化 DP 重算的过程。注意到，当处理一头新的、阈值为 $p_i$ 的奶牛时，并不需要对全部 $S$ 种不同的工作量重新做一遍背包。上一张 DP 表已经编码了此前所有奶牛的最优组合；当我们通过查询旧表来初始化新表时，这些旧奶牛的贡献实际上已经被计入了。

唯一新增的信息，就是这头刚刚加入的奶牛。因此，在用上一张表初始化完这 $S^2$ 个状态之后，只需要针对这头新奶牛的工作量 $w$ 和花费 $c$ 做一次背包扫描即可。于是，这一步的复杂度就变成了 $O(S^2)$。

这样一来，每头奶牛只需要 $O(S^2)$ 的时间，总复杂度就是

$$O(MS^2 + N \log N + M \log M).$$

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

const int S = 100;

void upd(ll& a, ll b) { a = min(a, b); }

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        ll n; cin >> n;
        vector<ll> a(n), oa(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
            oa[i] = i;
        }
        sort(oa.begin(), oa.end(), [&] (ll x, ll y) { return a[x] < a[y]; });
        ll m; cin >> m;
        vector<ll> l(m), s(m), v(m), o(m);
        for(int i = 0; i < m; i++) {
            cin >> l[i] >> s[i] >> v[i];
            l[i]--;
            o[i] = i;
        }
        sort(o.begin(), o.end(), [&] (ll x, ll y) { return l[x] < l[y]; });
        int pl = 0;
        vector<ll> dp(S * S, INF); dp[0] = 0;
        vector<ll> best(S + 1, 1e15);

        // computes expdp which is used to query
        vector<ll> expdp;
        int bsi = 1;
        auto compute = [&] (int nsi) {
            for(int si = 1; si <= S; si++) {
                if(best[bsi] * si > bsi * best[si]) {
                    bsi = si;
                }
            }
            expdp = dp;
            for(int i = 0; i < expdp.size(); i++) {
                if(i + nsi < expdp.size()) {
                    upd(expdp[i + nsi], expdp[i] + best[nsi]);
                }
            }
        };
        // uses expdp to query
        auto query = [&] (ll x) {
            ll d = x - pl;
            ll t = max((d - (ll)expdp.size()) / bsi + 1, 0ll);
            return t * best[bsi] + expdp[d - bsi * t];
        };
        int k = 0;
        int lasts = 0;
        vector<ll> ans(n);
        for(int i : o) {
            compute(lasts);
            while(k < n && a[oa[k]] < l[i]) ans[oa[k]] = query(a[oa[k]]), k++;
            vector<ll> ndp(S * S, INF);
            for(int j = 0; j < S * S; j++) {
                ndp[j] = query(l[i] + j);
            }
            for(int j = 1; j < s[i]; j++) upd(ndp[j], ndp[0] + v[i]);
            upd(best[s[i]], v[i]);
            lasts = s[i];
            dp = ndp;
            pl = l[i];
        }
        compute(lasts);
        while(k < n) ans[oa[k]] = query(a[oa[k]]), k++;
        for(ll i : ans) cout << i << " ";
        cout << endl;
    }
}