CF702F T-Shirts 笔记

由于价格无序，对于同一个人，快速对多个物品进行决策困难，因此考虑贪心从高质到低质每个物品，对所有人进行决策。

那么把人按钱数多少放到数轴上，每个物品就是对所有当前钱数 $\ge c$ 的人的钱减去 $c$，并让他们的答案 $+1$。

如果钱足够多，那么每次 $-c$ 后所有人的相对次序都不变，用数据结构很好做。但是相对次序改变就导致需要重构数据结构。

考虑优化。真正需要重构的部分是钱数 $\in [0,c)$ 的人没有变，和 $-c$ 后钱数 $\in [c,2c)$ 的人混在一起了，因此可以只重构这一部分，每次被重构的人钱数都至少减半，即每个人最多重构 $\log V$ 次，时间复杂度正确，为 $O(n\log n\log V)$，空间复杂度 $O(n)$。

上述操作用 FHQ Treap 很好处理，用 $\mathrm{key}$ 表示钱数即可。