题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）

可能场切了吧……就当我场切了吧。

手摸一下，发现不合法的充要条件为，存在一个 $w=2$ 的数 $x$，选到他之前的时候恰好花费了 $m-1$，并且在其之前有一个 $w=1$ 的数价值为 $y<x$，在其之后还有一个 $w=1$ 的数价值小于 $x-y$ 或者在其之后全都是 $w=2$ 的。

考虑枚举这个 $x$，然后想如何让其之前恰好花费 $m-1$，不难想到，原来就先于他的数操作后仍然先于其操作，并且会使消耗加一；原来不先于他但是先于 $\frac{x}{2}$ 的数，操作后会使消耗减一。因此相当于两部分选出来的数差一个值，范德蒙德卷积一下就可以 $O(1)$ 计算。然后再考虑在 $\frac{x}{2}$ 后面的部分，不妨枚举首个 $w=1$ 的位置，那么其之后状态一定，其之前任意，方案数是简单的；再预处理一部分东西就可以做到严格 $O(n^2)$ 了。

结束了……