题解：P2075 区间 LIS
N_z_
·
·
题解
@ship2077 没有实名认证，我来代投一下题解。
资料1
资料2
原题
介绍一种 $O(n\sqrt n\log n+q)$ 的做法，可以通过本题。
经典地，求 $lis$ 我们有一种二分贪心的方法，依次处理 $a_1,\cdots,a_n$，每次在一个集合中加入 $a_i$，然后删除一个大于 $a_i$ 的最小元素（如果没有不删除），最后集合的大小就是 $lis$ 长度。我们定义一个区间 $[l,r]$ 按这个操作执行的集合从小到大排的结果为 $A_{l,r}$，考虑如何刻画 $A_{l,r}$。
对于 $a=[10,3,4,9,1,5,7,2,8,6]$：
$A_{1,9}=[1,2,5,7,8],A_{2,9}=[1,2,5,7,8],A_{3,9}=[1,2,7,8],A_{4,9}=[1,2,7,8],A_{5,9}=[1,2,7,8],A_{6,9}=[2,7,8],A_{7,9}=[2,8],A_{8,9}=[2,8],A_{9,9}=[8]
A_{1,10}=[1,2,5,6,8],A_{2,10}=[1,2,5,6,8],A_{3,10}=[1,2,6,8],A_{4,10}=[1,2,6,8],A_{5,10}=[1,2,6,8],A_{6,10}=[2,6,8],A_{7,10}=[2,6],A_{8,10}=[2,6],A_{9,10}=[6],A_{10,10}=[6]
我们注意到 A_{l,r} 为 A_{l+1,r} 长度至多差 1 的子序列（归纳证明），于是我们定义 cnt_x 为元素 x 在 A_{1,m},A_{2,m},\cdots,A_{m,m} 中出现次数。知道 cnt_x 后我们可以轻松完成查询，注意我们查询时只需要关心 cnt_x 组成的集合。
当 m 变成 m+1 时，设当前加入的数为 x，考虑加入后改变的 cnt_x 为 p_0=x,p_1,p_2,\cdots,p_k，需要满足 p_i < p_{i+1} 且 cnt_{p_i} < cnt_ {p_{i+1}}，在此基础上 p_i 最小。新的 cnt'_{p_{i+1}}=cnt_{p_i}（cnt'_{x}=m+1）。cnt_x 组成的集合的修改量只有 O(1)。操作等价于 该题，于是我们能够做到 O(n\sqrt n\log n+q)。