T1

赛时打了一个 \(O(n^3)\) \(16pts\) 暴力和一个似乎可以过一个 \(20pts\) 特殊性质但其余无正确性的贪心。结果出来发现特殊性质挂了一个点，另一个地方还莫名其妙对了。说明特殊性质挂掉了，如果运气不好可能就挂到 \(16pts\) 了。考后看题解发现 \(O(n^2)\) 其实也是不难想的，有点可惜。

设 \(dp_{i, x, y}\) 表示考虑前 \(i\) 个数，第一个子序列最大值为 \(x\)，第二个子序列最小值为 \(y\) 时的答案，暴力转移复杂度 \(O(n^3)\)。

观察发现，对于 \(dp_{i,x,y}\)：

• 如果 \(x>y\)，则之后的位置两个序列的选择已经互不影响，可以直接预处理后缀 LIS 和 LDS，可以直接得到答案。将这种状态称为无效状态。

• 如果 \(x<y\)，则第一个序列的所有元素都小于第二个序列的所有元素。意味着 \(y\) 即是 \(x\) 在 \(a_{1\sim i}\) 中的后继。故对于每个 \(i\) 只有 \(i\) 个状态，共 \(O(n^2)\) 个状态。可以做到 \(O(n^2)\) 的时间复杂度。

对于无效的状态，不妨设 \(dp_{i-1,x,y}\) 转移到了 \(dp_{i,x,a_i}(x>a_i)\)。则答案为 \(dp_{i-1,x,y}+1+LIS_{i,x}+LDS_{i+1,a_{i+1}}\) 其中 \(LIS_{i,x}\) 表示 \(a[i\sim n]\) 中只考虑 \(\ge x\) 的数时的 LIS。LDS 类似。

这个式子中 \(LDS_{i+1,a_{i+1}}\) 在 \(i\) 一定时不变。而 \(LIS_{i,x}\) 在 \(x\) 上的变化（\(LIS_{i,1},LIS_{i,2}\dots,LIS_{i,n}\)）相当于 \(O(n)\) 段区间加（转化成倒序求 LDS 后当前数值和被替换的数值之间的值会 \(+1\)，可以画个图理解）。

于是可以用线段树维护有效状态中 \(dp_{i,x,y}+LIS_{i+1,x}\) 的值。

对另一种情况的操作类似。

时间复杂度 \(O(n\log n)\)。