题解：AT_arc186_c [ARC186C] Ball and Box

设选盒子的人为 A，选球的人为 B。显然，A 在还有位置装一个球的时候一定不会买新的盒子，所以游戏停下的位置一定一开始或者某一种颜色的球的箱子装满时。A 的最优策略看起来比较难考虑，但B的就很简单了：如果 A 还没有一种颜色的球，直接选那种颜色的球；否则选盒子容量最小的那种颜色的球。

那么 A 最后选出来的盒子里面，容量前 $m-1$ 大的盒子一定都只有一种颜色的球，后面的盒子一定会装满。否则，在它们即将装不只一个球的时候，B 可以把那个球的颜色改为目前还没有选过的那种颜色的球。

我们将盒子按容量降序排序。设 A 最终选的容量第 $m-1$ 大的箱子在 $k$。那么 $[1,k]$ 的箱子里就只有一个球，$(k,n]$ 的箱子里都会放满 $v_i$ 个球。

枚举第 $m$ 大的箱子的位置，$(k,n]$ 的箱子的最大贡献用后缀最大值是容易维护的。$[1,k]$ 的 $m-1$ 个箱子每个都只有 $1$ 的贡献，所以只要选 $p_i$ 前 $m-1$ 小的箱子即可。维护的方法应该不少，我用的是权值线段树。

注意一下 $m < n$ 和 $m \le 1$ 的情况。

Submission。