LOJ链接

UOJ链接

题解

设$H_{l,r,x}$为只考虑区间$[l,r]$，所有柱子的高度都不超过$x$的方案数。我们可以枚举从它出发能走遍整个区间的那个柱子$m$，设计出一个暴力的DP：$H_{l,r,x}=\sum\limits_{m}H_{l,m-1,x}H_{m+1,r,x-1}$。此处$m$不仅要在区间的中间部分，还要满足它可以是当前这个高度。可以发现，对于任意长度的区间，可选的$m$的数量都不超过$3$。每个柱子可以选择的高度范围将正整数分成了许多段，同一段内的高度是否能被柱子选择的情况都是相同的。我们可以猜想$f_{l,r}$在每个段内都是不超过$r-l+1$次的多项式，并且以下做法可以证明这个结论。

从小到大考虑高度的每个段。设当前段为$(a,b]$，区间$[l,r]$的所有柱子高度都不超过$a+x(x \in \mathbb{N})$的方案数为$f_{l,r,x}$。我们通过存储关于$x$的$r-l+1$次多项式来表示$f_{l,r}$。

此时我们已经在之前的段中算好了$f_{l,r,0}$。$f_{l,r,x}=f_{l,r,x-1}+\sum\limits_{m}f_{l,m-1,x}f_{m+1,r,x-1}(x > 0)$。可以发现，若$f(x)$是一个$k$次多项式，则$f(x+a)$也是$k$次多项式，且$\sum\limits_{i=0}^{x}f(i)$是$k+1$次多项式。这样我们就能知道$f_{l,r,x}$确实是一个$r-l+1$次多项式。 将当前高度区间的长度代入多项式中就能得到所有柱子的高度都在当前段及以下的情况下区间$[l,r]$的方案数。

有用的区间是很少的，我们可以采用记忆化搜索。分析这种做法的复杂度：每次递归时可能的$m$不超过$3$个，递归到的长度为$\frac{n}{2^k}$的区间不超过$3^k$个。因此，若我们对长度为$l$的区间花费的时间为$O(l^2)$，则处理每个高度段的复杂度不超过$\sum\limits_{k \geq 0}(\frac{n}{2^k})^2 \cdot 3^k=n^2 \sum\limits_{k \geq 0}(\frac{3}{4})^k=O(n^2)$，总复杂度不超过$O(n^3)$，可以通过本题（也许要卡常）。

我们有充足的时间可以进行复杂度可能很高的预处理，维护多项式并在$O(n^2)$的时间内支持乘法、平移、求前缀和的方法很多，比如：

1. 维护点值
2. 维护牛顿级数
3. 维护系数

笔者认为前两种做法比较好写，并且采用了第二种方法。需要注意的是，在维护点值时，不能对每个区间都维护$n+1$个点的值，而是应该维护区间长度$+1$个点的值，并在需要升高次数的时候暴力把剩下的点的值插出来。

牛顿级数

定义$\binom{n}{m}=\begin{cases} \frac{n^{\underline m}}{m!} && m \geq 0 \\ 0 && m < 0 \end{cases}(m \in \mathbb{Z})$，$\Delta f(x)=f(x+1)-f(x)$。则$\Delta \binom{x}{m}=\binom{x}{m-1}$。

任何一个$k$次多项式$f(x)$都可以表示为$\sum\limits_{i=0}^{k}c_i\binom{x}{i}$。且$\Delta ^d f(x)=\sum\limits_{i=0}^{k} c_i \binom{x}{i-d}$（其中$\Delta ^d$表示取$d$次$\Delta$）。因此，$\Delta^d f(0)=c_d$，我们可以通过这个等式来$O(k^2)$计算将多项式表示成牛顿级数时的$d$次系数。

我们可以将以牛顿级数的形式表示的多项式在$O(n^2)$的时间内在系数表达和点值表达之间转换，将以点值表达的牛顿级数进行平移时简单的。因此，我们可以用牛顿级数来维护本题中的多项式。

AC代码

NOI的时候我写的是$O(n^5)$的分段容斥DP，只得了$60$分……突然发现把直接DP改成记忆化搜索就能得$95$分，心态炸了。