题解：P14636 [NOIP2025] 清仓甩卖 / sale

特判 $m=1$。先考虑正难则反，把会没掉的方案数算出来。

对 $a$ 从大到小排序。考虑枚举一个 $i$ 满足 $w_i=2$，此时任何 $j<i,w_j=2$ 以及 $2a_k>a_i,w_k=1$ 的糖果 $j,k$ 都会被选中。注意根据定义，$i$ 不会被选中。那么，没掉的方案有两种可能：

对于第一种情况，枚举 $w_i=2$ 的 $i$，以及 $a_j$ 最小（也就是 $j$ 最大）的 $w_j=1$ 的糖果 $j$。这个 $j$ 需要满足：

此时，这个方案能产生贡献当且仅当 $a_j<a_i$。把上面的东西判完之后对这样的方案计数：

对于第二种情况，枚举 $w_i=2$ 的 $i$，以及上文提到的 $l,o$。此时需要满足：

此时，这个方案能产生贡献当且仅当 $a_l+a_o<a_i$。把上面的东西判完之后对这样的方案计数：

现在，如果我们知道怎么求 $d_{i,j}$，那就可以 $O(n^3)$。在求 $d$ 之前，我们先把第二种情况优化一下，使得除去求 $d$，剩下的复杂度为 $O(n^2)$。

我们发现，第二种情况的 $o$ 可以扔到外面去，具体地，固定 $i$，随着 $l$ 的增加，满足条件的 $o$ 一定是个后缀，而这个后缀的边界会越来越向左，直到边界撞上 $\max(i,l)$ 为止。撞上之后，任何 $o>l$ 的 $o$ 都将满足条件。因此我们拿个指针维护这个边界，随着边界向左扩张动态维护当前的总方案数就可以了。

问题变为了求 $d_{i,j}$。

至此我们完成了本题，时间复杂度 $O(n^2)$。