假如我们翻转 $[l,r]$ 这个区间,不降子序列中第 $x$ 个位置是最后一个 $1$。
若 $f(i)$ 表示原序列 $1\sim i$ 中 $1$ 的个数。
若 $g(i)$ 表示原序列 $i+1\sim n$ 中 $2$ 的个数。
若不考虑翻转,答案就是 $f(x)+g(x)$ 的最大值。
只有 $x\in[l,r]$ 才会对答案有优化作用。
所以考虑翻转后的序列,满足:
- $f’(x)=f(l-1)+f(r)-f(x)$
- $g’(x)=g(l)+g(r+1)-g(x)$
- $ans’_x=f’(x)+g’(x)=f(l-1)+g(l)+f(r)+g(r+1)-ans_x$
预处理出 $f(x-1)+g(x)$ 和 $f(x)+g(x+1)$ 的前缀和后缀最大值。
扫一遍,看看什么时候取得最大值。