题解：P11924 [PA 2025] 贪婪大盗 / Piracka Chciwość

遗憾离场。看上去像个分析性质题，实际上比较暴力。

首先暴力从后向前模拟，维护 $f_i$ 表示当前想让这个人同意的话，需要分给他 $f_i$ 个金币。显然从小到大选，复杂度是 $\mathcal O(n^2\log n)$。

核心性质是每个人分得的钱数一定不会超过 $\max(a)$（记为 $w$）。证明就是在 $i\rightarrow i-1$ 的时候，令 $S_{i-1}=[i-1,n]\setminus S_i$ 一定合法。

所以用线段树维护集合 $A_{i,j}$ 表示如果当前想让他同意，需要花费 $i$ 个金币，贪婪值等于 $j$ 的点的位置集合。

处理到 $i$ 的时候，从小到大枚举金币数量，什么时候需要的总和大于 $m$ 了或者人数合法了就停下。然后很讨厌的限制是金币相同的话编号从大到小选，所以确定了给出的最大金币数 $k$ 后，$<k$ 的所有人都要选，然后所有 $=k$ 的人选的是一段后缀。所以在所有 $A_{k,\ast}$ 上同时进行一个线段树二分，即可找出需要的区间。

这样操作就是，对于不选的人，金币数全部归零，然后所有人的金币数都加上各自贪婪值。这里会发生若干合并和分裂，需要线段树合并和分裂实现。这样是 $\mathcal O(na^2\log n)$ 左右。

注意到一个人清零之后，金币数就一定是他自己贪婪值的倍数，所以对于还没被清零过的数暴力处理（一个人最多被暴力处理 $256/a$ 次），然后需要维护的线段树棵数是 $\mathcal O(a\log a)$ 级别的。这样复杂度可以优化到 $\mathcal O(n(a\log a+d(a)\log n))$，实际远远跑不满。