T4:
题目大意:
定义一个数组 \(a\) 是良好的,当且仅当可以选择若干个(可以为 0)不交的区间,将他们内部 reverse 之后升序。
给定 \(n\) 和排列 \(a\),对于每个 \(k\),求有多少子序列不包含 \(a_{k}\) 且是良好的。
\(n \le 3 \times 10^3\)
解题思路:
考虑刻画一个良好的数组,发现一定能将其分为若干段,使得段内倒序,段之间正序,且互不相交。
这显然是一一对应的。
f
由于 \(n \le 3000\) 且合法性与相邻的有关,所以考虑 dp。
自然的,设 \(dp_{i,j}\) 表示前 \(i\) 个数,最大值为 \(j\) 的方案数。
转移可以直接用前缀和优化,而且 \(i,j\) 内部可以预处理 \(f_{i,j}\),表示 \(i\) 开头, \(j\) 结尾的递减子序列的方案数。
\(O(n^2 \log n)\)。
我们要算每一个 \(x\),求不包含 \(x\) 的方案数,但我们发现枚举完 \(x\) 之后要合并前后缀,但直接做是 \(O(n^3)\) 的。
因为不包含 \(x\) 需要在 \(y \ne x\) 时更新,而这样是不好更新的,所以考虑拿整体减去经过 \(x\) 的方案。
那么我们枚举 \(l,r\) 表示 \(x\) 所在的段内的开头和结尾,那么内部的方案数是 \(f_{l,x} \times f_{x,r}\),而外部的则是 \(pre_{l - 1, a_{r} - 1} \times suf_{r + 1, a_{l} + 1}\)。
其中 \(pre\) 和 \(suf\) 分别为做一遍前缀/后缀 \(dp\) 的二维前缀和。
但是这些数看起来都是相互关联的,而 \(pre\) 和 \(suf\) 的结构比较复杂,所以考虑优化一些 \(f_{l,x} \times f_{x,r}\) 之类的东西。
由于 \(n \le 3000\),也就是说我们有枚举两个值的机会,考虑先枚举 \(l\) 试试。
因为 \(x \le r\),所以后面的能影响前面的,而且前面的不影响后面的。
所以我们倒着枚举 \(x\),看一下后面的 \(x\) 作为 \(r\) 时对前面的 \(x\) 有什么影响。
对于后面一个 \(r\) 对于当前点的影响,我们可以发现只有 \(f_{x,r}\) 不确定,但是我们发现 \(f\) 是可以递推的,所以将不同的 \(r\) 赋一个对应的权值,相加即可。
\(O(n^2 \log n)\)