给定长度为 \(n(n \le 2000)\) 的序列 \(a\)，询问有多少个子序列满足不存在长度 \(\ge 3\) 的下降子序列。
显然可以 DP，令 \(dp_{i, j, k}\) 表示前 \(i\) 个数组成的子序列，最大值为 \(j\)，长度为 \(2\) 的下降子序列第二个元素最大的为 \(k\) 的方案数。考虑转移：
- 若 \(a_i < k\)，形成了长度为 \(3\) 的下降子序列，不能转移。
- 若 \(k \le a_i < j\)，\(dp_{i, j, k} \rightarrow dp_{i, j, a_i}\)。
- 否则，\(dp_{i, j, k} \rightarrow dp_{i, a_i, k}\)。
然后你就得到了一个 \(O(n ^ 3)\) 的做法，可以通过 D1。
考虑优化，不难发现对于每个 \(i\) 转移时只会贡献到最多 \(2n\) 个状态。于是可以枚举这 \(2n\) 个状态，使用树状数组维护转移即可（单点加，求前缀和）。时间复杂度：\(O(n^2 \log n)\)。
一些细节：开两个树状数组分别维护 \(j\) 固定和 \(k\) 固定的 DP 值。
此题观察到转移只会贡献 \(2n\) 个状态就很简单了。