题解：P2075 区间 LIS

· · 题解

好题。

LIS 有直接 dp 的做法，但是这个东西感觉做不了，于是这里有个很厉害的刻画方式。

维护一个集合 S，从 1 到 n 一次加入 a_i，找到第一个大于它的数（大于它的最小的数）删除，如果没有则不删，然后加入它，最后答案就是集合大小。

这个看起来非常不对，就像自己看错了一样。但是手玩一下发现答案对上了，让我们来试着分析一下它。以下是分析过程，如果想直接看分析出来的结论可以跳过。

首先从贪心意义上讲，找到第一个大于它的数删除是对的，因为当前加入的数在相同大小的 LIS 中它作为头部是比第一个大于它的数优的，那要是还有个更小的数介于两者之间导致第一个大于它的数作为头部的 LIS 更长怎么办？我们仔细想想发现并不会存在这种情况，因为这与我们的策略冲突。

那加入的数有没有机会再删别的数呢？没有机会，对于更大的数，它代表的 LIS 也一定长于当前加入的数代表的 LIS，代表就是作为头部的意思。这也是稍微分析就能得出的，但是我们依然不知道该算法整体为何是对的。

但是灵光乍现，我们发现集合中每个数代表的 LIS 长度都不同，进一步的，他们的长度分别是 1,\cdots,|S|，再进一步我们发现其中最小的数代表 1，次小的数代表 2......于是一切都解释得通了！它本质上是个依据单调性优化 dp 的过程，能刻画出这种策略的人真不一般！

然后关于本题这么做，我们考虑扫描线，扫到 i 时，显然我们并不能直接对每个集合进行维护，我们设 S_{l,r} 表示区间 [l,r] 执行该算法的最终集合，我们发现对于固定的 r 关于 l 有类似单调性的性质，我们发现 S_{j,i} 与 S_{j+1,i} 的大小差距不大于 1，且 S_{j+1,i} 是 S_{j,i} 的一个子序列，这意味着每个元素的出现集合是一个前缀，我们扫到 i 时维护每个元素 x 的前缀 b_x， 表示其位置，我们考虑加入 x 带来的改变，对于第一个大于 x 的元素一点机会都没有啊，直接寄了，其前缀变为 0。而对于后面的数以此类推，我们发现改变的位置可以用一个序列 c 表示，满足 c_0=x,c_i>c_{i-1},b_i>b_{i-1}，且 c 字典序最小，改变是 b_{c_{i}}=b_{c_{i-1}}，b_x=i。

我们在一个序列上做，初始 v=0，j 从 x 开始从小往大枚举，若 b_j>v 则交换它们的值。

我们发现这种修改对于整个集合而言是一个大根堆，那么我们考虑分块，散块重构整块用大根堆维护，并打 tag，标记是一个集合，用小根堆维护，重构时用。

用树状数组维护前缀贡献，每次修改只有 \mathcal{O}(1) 次，总复杂度 \mathcal{O}(n\sqrt n\log n+q\log n)。