Again Counting Stars 糖糖做法

前面的转化不说了，现在要解决的问题如下：

给出单调不增数组 $s_1, \ldots, s_{n-1}$，你需要对每个 $1 \leq p \leq n$ 计数有多少个数组 $b'_1, \ldots, b'_{n-1}$ 满足：

这里和官方题解是完全反着的，相当于做的是后缀和而不是前缀和。

然后把序列 reverse，相当于 $s$ 和 $b'$ 都是单调不降的。

这个时候就相当于要对于每个 $i$ 计算 $b'_i$ 是第一个 $b'>s$ 的位置的方案数，以及 $b'_i$ 是最后一个 $b'>s$ 的位置的方案数。称前者为 $A_i$，后者为 $B_i$。

我们考虑暴力 dp 是怎么做的，相当于记录 $f_{i,j}$ 表示 $b'_i=j$ 的方案数，然后转移是先做前缀和再删掉一个前缀。

我们熟知对多项式求前缀和还是多项式，但是删掉一个前缀的处理比较烦。

于是考虑不要求不合法的位置是 $0$，只保证合法的位置的值是对的。

此时相当于 $F(i)$ 变成 $F$ 在 $l\sim i$ 的前缀和，$l$ 是没被删的最小位置。

可以看出 $F$ 显然是多项式，于是直接维护连续点值拉插可以做到 $O(n^2)$ 求一个 $A_i$ 以及 $i$ 作为起点对每个 $B_j$ 的贡献。

于是求一个 $B_i$ 相当于对所有 $j$ 求它们作为起点的贡献和，相当于维护 $F$ 之后多一个加入 $s_i$ 这个新起点的转移，也就是全局 $+1$。

于是求所有 $B_i$ 可以做到 $O(n^2)$，而求所有 $A_i$ 就直接把做法转置就好了。

这样我们可以跑出最优解 $7$ 倍的时间。