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

相信自己的做法不会有错，并不复杂。场上通过所有大样例。

首先统计是最优的肯定不好做，考虑统计不是最优的，然后用总方案数减去。

发现这种情况就是在只剩两块钱的时候，先选了价格 $1$ 的物品 $A$，后面买不了价格 $2$ 的，只能再选一个价格 $1$ 的物品 $B$ 或者没有能买的了。

这时候不一定最优，因为如果不选 $A$，直接就买一个价格 $2$ 的物品 $C$ 可能更优秀。

考虑枚举 $A$，设为 $a_i$。设 $C$ 为 $a_k$，则要求 $a_i>\frac{a_k}{2}$，原因是我们在面临这两个物品的时候先选了 $A$（性价比高）。

先将物品排序，二分得到 $k\in [i+1,p]$。

接着枚举 $B$，设为 $a_j$，则有 $j<i$，且 $a_i+a_j<a_k$（我们要求其不优）。

现在要求预处理后，已知 $i,j$，可以 $O(1)$ 算出方案数。

把刚才的不等式再拿出来：$a_i+a_j<a_k<2a_i$，发现合法区间变成 $k\in [l,p]$，$l$ 可以双指针得到。

我们在枚举 $i$ 之后，可以先枚举每个 $k$ 对应的方案数，这里的方案数只考虑 $[i+1,n]$ 的价格取值，由于已经知道 $i,k$，可以再结合一个性质推出各个区间有多少个 $1$ 和多少个 $2$，这个性质就是：单独考虑价格为 $1$ 或 $2$，选取的物品都是一个后缀。而显然，$k$ 是从后往前第一个没选的 $2$。所以就很好算了。

设 $k=x$ 的时候 $[i+1,n]$ 的价格取值方案数为 $cnt_x$，则求出 $cnt$ 的后缀和 $suf_x=\sum_{t=x}^p cnt_t$ 即可快速得到 $k\in [l,p]$ 的方案数总和。

接下来考虑 $[1,i-1]$ 的价格取值方案（显然我们已经钦定了 $i$ 填 $1$），在 $[j+1,i-1]$ 中，必须都填 $2$，这样才能保证选完 $A$（$a_i$）后我们会选择 $B$（$a_j$），而在 $[1,j-1]$ 中，填什么是无所谓的，所以我们的方案数就是 $suf_l*2^{j-1}$。

现在似乎做完了，但是还要考虑不存在 $B$ 的情况（$\forall 1\le j\le i-1,w_j=2$），情况类似，方案数就是 $suf_{i+1}$。

时间复杂度 $O(n^2)$。