信友队 CSP-S2023 B

注意到关键性质 \(a_i\) 是 \(a_{i+1}\) 的因数，故小决策在 \(\frac{b_j}{a_j}\) 更大时是严格优于大决策的，而 \(a_j\) 相同的决策之间显然只有 \(b_j\) 最大的有用，故最终至多只会保存 \(O(\log m)\) 个有决策。

对于倍数增量的东西一定要敏感，多联系到量级上。

然后考虑如何处理询问。

对于单个 \(f\)，我们一定会考虑按 \(a_j\) 从大到小依次使用有效决策集合中的决策。此时我们可以将每个决策的贡献拆开，把 \(\forall i\ge 2\) 的决策 \(i\) 的贡献 \(b_i\) 拆成 \(b_i-b_{i-1}\times \frac{a_i}{a_{i-1}}\)，表示每 \(b_i\) 个物品可以少花的钱数。这样的好处是，对于固定的 \(f\)，我们可以在 \(O(1)\) 的时间复杂度内算出任何一个决策的贡献，而原本只能在 \(O(\log n)\) 内算出所有决策的贡献之和。

题中需要求出前缀 \(f\) 之和，此时对于每个决策的贡献其实就是一个以 \(b_j\) 为单段长度、段与段之间数值呈等差序列、最后还有余数长度贡献的状物，式子列出来求一下即可，时间复杂度 \(O(q\log m)\)。

尽可能将决策的贡献拆的独立。