AtCoder Beginner Contest 360 G - Suitable Edit for LIS 题解

[ABC360G] Suitable Edit for LIS 题解

前言

第一次场切 G（虽然被 after_contest 叉了），纪念一下。

思路

贪心地，考虑最优秀的操作一定是修改中间的一个元素，把左右两边的 LIS 接在一起。

于是可以预处理每个以每个下标 $i$ 开头 / 结尾的最长 LIS 长度 $R_i$ 和 $L_i$，然后枚举右边 LIS 开头的下标 $r$，代表修改 $a_{r-1}$ 的值，则答案为 $\max^{n+1}_{r=2}\{R_r+\max_{l=0}^{r-2}\{L_l\}(a_l+1<a_r)+1\}$。

预处理和统计答案使用离散化 + 线段树优化 dp 实现即可，时间复杂度为 $\mathcal{O}(n\log n)$。

需要注意的是统计答案时，应先将 $a_0$ 设为极小值，$a_{n+1}$ 设为极大值，这样就可以分别覆盖到左边的 LIS 为空和右边的 LIS 为空的情况，after_contest 叉的也就是这两种边界情况。

代码

link