题面链接

题解

题目意思有点不好懂，其实就是在数列中找到与 A_{i-1} 相邻的两项来限制 A_i 的值，问方案数。

首先凭感觉，感觉越往后面的数可能的情况是更少的，整体呈收束趋势。

我们设用来更新 A_i 的 L 和 R 为 L_i 和 R_i ,根据定义有 L_{i-1} \leq A_{i-1} \leq R_{i-1} ，现在考虑更新 A_i ，根据定义有 L_{i-1} \le L_i \leq A_{i-1} ， R_{i-1} \ge R_i \ge A_{i-1} ，即L_{i-1} \leq L_{i}, R_{i-1} \geq R_{i} 。

这种收束的性质会为我们后面的dp转移提供便利。

考虑设计一个很朴素的状态，即 f_{i,k,l,r} 表示当前填到第 i 个数，A_1 到 A_{i-1} 中小于等于 k 的最大的数为 l ，大于等于 k 的最小的数为 r

转移时有以下几种情况：

1. $k,l,r$ 不相等， $A_{i-1}$ 要么是 $l$ 要么是 $r$ ，

f_{i, k, l, r} = \sum_{j \leq l} f_{i-1, l, j, r}+\sum_{j \geq r} f_{i-1, r, l, j}

2. $k=l=r$

若 A_{i-1}=k 那么f_{i,k, k, k} = \sum_{j \leq k} \sum_{z \geq k} f_{i-1,k, j, z}

否则，
f_{i,k,k,k}=\sum_{y\ne k}(\sum_{z\le y}f_{i-1,y,z,k}+\sum_{z\ge y}f_{i-1,y,k,z})
(y不等于k，不知道为什么latex乱掉了……)

这个 O(nr_i^4) 的做法肯定会T，可以用前缀和达到 O(nr_i^3) 计算发现过不了，但是实际上最大的点都能过，也许是我时间复杂度算错了吧。

代码