CF605D 题解

· · 题解

题目大意

给一个长度为 n 的序列。

每次在原序列做一个操作，把 a_i 修改成 k。

问每次操作后序列的最长上升子序列长度。

思路

首先 LIS 有个 O(n \log n) 的做法。

我们可以求出以第 i 个数结尾的 LIS 长度 d_i。

同理反着求一遍也可以求出以第 i 个数开头的 LIS 长度。

回到本题，对于每次修改 a_i = x；

很显然有 2 种情况：

  1. 新的 LIS 包含 a_i。
  2. 新的 LIS 不包含 a_i。

我们先求一定包含 a_i 的 LIS。

我们预处理出以第 i 个数结尾的 LIS left_i，和以第 i 个数开头的 LIS right_i。

我们只要求出左边 \max(left_j) （且 j<i，a_k<x） 和右边 \max( right_j) （且 j>i，a_j>x），两者长度相加再加 1 就是包含 a_i 的新 LIS。

如果这个值大于原序列的 LIS，那它一定是答案。

再分析 LIS 不包含 x 的情况。

如果修改的数必须在原序列的 LIS 中，则不包含修改的数的 LIS 一定会减少 1。

如果修改的数可以不在原序列的 LIS 中，不包含修改的数的 LIS 则不会变化。

问题就变成了对于序列中的每个数，判断其是否必须出现在 LIS 中。

先用之前的思路算出包含 a_i 的 LIS：

len_i = \max(left)+1+\max(right)

如果 len_i = 原序列的 LIS，那么 i 可能出现在 LIS 中。

如果 i 可能出现：

又如果存在 j<i 且 a_j \ge a_i 且 j 可能出现在 LIS 中，i 有可以不出现在 LIS 中。

同理如果存在 j>i 且 a_j \le a_i 且 j 可能出现在 LIS 中，那么 i 可以不出现在 LIS 中。

所以如果 i 不满足可以不出现在 LIS 中的条件，则 i 一定出现在 LIS 中。

则对于每次修改 a_i=x，先计算包含 x 的 LIS 长度。

如果比原序列 LIS 大，则一定是答案。

否则，如果 i 可以不出现，则 LIS 不变，否则如果 i 一定出现，则 LIS 会减少 1。

回过头来，考虑计算 \max(left_j（且 j<i，a_j<x）

这个就是经典二维数点问题。

对 a_j 和 x 排序。 从小到大枚举 x，把 a_j<x 的 left_j 插入树状数组的第 j 个位置。

我们把维护更新和询问树状数组的加法变成求 \max。

问题转化成求前缀最大值。