「Solution」2022-11-21 AGC 056 B

link

写篇人能看懂的题解。

看到要对下标序列计数，无法直接做，因为当你拿到 $x$ 时，第一步需要将它转化为 $p$ ，在才能进行是否合法的判断，那么就考虑对 $p$ 计数。发现一组 $x$ 会对应着多个 $p$ ，如果直接对 $p$ 计数和原问题并不等价。

首先处理使得 $x$ 和 $p$ 构成一一对应的关系。构造一组 $p'$ ，具体的构造方式是，考虑从 $n$ 到 $1$ 依次加入这个序列，且每次选择的位置都是最靠前的那个，此时的 $p'$ 一定是唯一的，那么对 $p'$ 计数就和原问题等价了。

问题变成对 $p'$ 计数，计数方式和构造方式类似，考虑加入最大值，位置为 $pos$ ，那么此时包含该点的最大值已经确定了，且 $[1, pos)$ 和 $(pos, n]$ 的子问题是与原问题相同且独立的，可以区间 $dp$ 或者记搜处理掉。

定义 $dp_{l, r, k}$ 表示 $[l, r]$ 中最大值的位置最靠前在 $k$ 处时的方案数，那么转移就为 $dp_{l, r, k} = dp_{l, k - 1, k - 1} \times dp_{k + 1, r, k + 1} + dp_{l, r, k + 1}$ 。似乎很对，但其实会算重，问题在于对 $p'$ 的计数必须是在保证了从大往小考虑每个数尽量往前放的前提下才会和原问题等价。此时算重了，就说明在考虑某些数时位置还可以继续往前面放，即是说放完当前的数在 $k$， 存在一个位置 $k', k' < k$ ，且 $k'$ 和 $k$ 没有被包含在任意一个 $[l_i, r_i]$ 中，那么这时，就不能再往 $[k', k)$ 中的位置放数，因为一旦其中放了一个更小的数，$k$ 位置上的数就可以和这个数互换位置，导致与条件的矛盾。于是，应该预处理一个 $pos_{l, r, k}$ 表示与 $[l, r]$ 相交的所有限制区间中包含位置 $k$ 的最左的端点的位置。

最后得到：

$$ dp_{l, r, k} = dp_{l, k - 1, pos_{l, r, k}} \times dp_{k + 1, r, k + 1} + dp_{l, r, k + 1} $$