「ZJOI 2016」线段树（动态规划）

题目大意

「ZJOI 2016」线段树（Luogu 3352）

有一个长度为 $n$ 的数列 $a_1, a_2, \cdots, a_n$。进行 $q$ 次操作，每次随机选出一个区间，然后把区间中的所有数赋值为区间的最大值。问最后每一个位置上的数的期望乘上所有可能操作个数后$\bmod 10 ^ 9 + 7$ 是多少。

数据范围：$n, q \le 400$。

思路分析

算法一

由于数很大，我们先将序列离散化。我们假设数列已经离散化完毕，并且数列中等于 $i$ 的数原来是 $\text{val}(i)$。

对于每个 $x$ 分别考虑它最后在每个位置出现了几次。令 $\text{dp}(x, i, l, r)$ 表示 $i$ 次操作过后，$a_l, a_{l + 1}, \cdots, a_r \le x$，$a_{l - 1}, a_{r + 1} > x$，即 $[l, r]$ 是极长的 $\le x$ 区间的方案数。

考虑第 $i$ 次选择的区间：

• 若它完全在原区间内部或外部，则原区间不会变化。
• 若它横跨原区间的左端点，但是不经过右端点，那么新区间的右端点不变，左端点向右移动到选择的区间的右端点 $+ 1$ 处。
• 若它横跨原区间的右端点，但是不经过左端点，那么新区间的左端点不变，右端点向左移动到选择的区间的左端点 $- 1$ 处。
• 若它包含整个区间，那么原区间就会消失。

综上所述，我们可以列出 DP 的转移方程：

$$\text{dp}(x, i, l, r) = g(l, r) \times \text{dp}(x, i - 1, l, r) + \sum_{1 \le j < l} (j - 1) \times \text{dp}(x, i - 1, j, r) + \sum_{r < j \le n} (n - j) \times \text{dp}(x, i - 1, l, j)$$

其中 $g(l, r)$ 表示对区间 $[l, r]$ 没有影响的操作区间个数。

使用前缀和优化即可达到 $O(n ^ 2 q)$ 的复杂度。由于有 $n$ 个不同的 $x$，总复杂度为 $O(n ^ 3 q)$。

那么对于一个位置 $i$，它 $\le x$ 的情况数就是 $\sum_{i \in [l, r]} \text{dp}(x, q, l, r)$。我们记这个数为 $f(i, x)$，位置 $i$ 等于 $x$ 的方案数就是 $f(i, x) - f(i, x - 1)$。所以位置 $i$ 的最终答案为：$\sum_{x} \text{val}(x) \times (f(i, x) - f(i, x - 1))$。

期望得分 $70$ 分。

算法二

我们考虑在算法一的基础上优化。发现复杂度瓶颈在于一开始的枚举 $x$，我们应该去掉这个过程。注意到对于 $f(i, x)$，它对位置 $i$ 有 $\text{val}(x) - \text{val}(x + 1)$ 的贡献。于是我们不必枚举 $x$，只需要在一开始给 DP 赋初始值的时候将贡献加进去即可。也就是说，对于每个 $x$，找出它对应的极长区间，然后让 $\text{dp}(0, l, r) \leftarrow \text{dp}(0, l, r) + \text{val}(x) - \text{val}(x + 1)$。这样的复杂度就减小到了 $O(n ^ 2 q)$。详见代码。

期望得分 $100$ 分。

代码实现

算法一（70 分）

#include <cstdio>

算法二（100 分）

#include <cstdio>