题目大意
有 $n$ 个空白方格从左到右排成一行，编号以此为$1..n$。小爱可以给每个格子填上一个数字，其中对于编号为 $i$ 的格子，可以填入的数字的范围为给定的 $[l_i,r_i]$。
现在，小爱想知道，如何选择合适的填法，才能使填入后这 $n$ 个数字组成的序列 $a_1,a_2,a_3,...,a_n$ 的最长上升子序列上度最长，本题只需输出最长长度即可。
数据范围
$1 \le n \le 10^5 , 1 \le l_i \le r_i \le 10^9$
算法思路
可以想到这是一个变种的最长上升子序列$dp$问题，由于数据范围较大，定是需要思考$O(nlogn)$算法，但不妨碍我们从简单思路出发来探究问题。
我先用普通最长上升序列算法来设计$dp$状态， $dp[k]$ 长度为$k$的最长上升子序列的结尾的填入数字的最小值。对于变种最长上升子序列问题，也很容易想到$dp$数组是单调递增的，构建长度更长的序列，一定也需要更大的结尾数字。
假设从前$i-1$号格子已经就算出了一段$dp$数组,$curMax$为当前计算出的最后一项的下标，注意下标也代表这最大上升长度。
考虑第$i$格子时，有如下几种情况：
- $l_i > dp[curMax]$，则$dp[curMax+1] = l_i$。
- $l_i == dp[curMax]$ 且 $l_i < r_i$，则$dp[curMax+1] = l_i + 1$。
- $l_i == dp[curMax]$ 且 $l_i == r_i$, 则无需更新。
- 在$dp$数组中找到大于 $l_i$ 最小位置 $x$，找到小于 $r_i$ 的最大位置 $y$。
若$x <= y$, 则 $i$ 格子加入使得 $[x,y]$ 区间内最长上升序列长度都加一，且最小结尾数字只需加一即可。做法上我们使区间内所有数字加一，并向后平移一个位置。平移之后，x位置会有空缺。若$l_i > dp[x-1]$, $dp[x] = li$, 否则 $dp[x] = l_i + 1$。 - 若$x > y$，则说明 $l_i$ 只能更新位置 $x$ 的最小结尾数字若$l_i > dp[x-1]$ , $dp[x] = l_i$ ，否则若$r_i > l_i$,$dp[x] = l_i+1$ 。
由于$dp$数组是单调的所以$x$ 和 $y$ 位置都可以二分拿到。唯一头疼是第$4$种情况下，区间更新和平移数组非常耗时。有没有一种数据结构，可以动态插入数据到指定位置，相当于平移指定位置后面的数据，且能够对指定区间元素实现统一的操作呢？
平衡树（带区间操作）
有，不过我们需要手写平衡树。可能你也听过一些平衡树，比如红黑树，树堆Treap，伸展树Splay等等吧。在这里推荐新手们，学一学FHQTreap，范浩强大神提出的一种无旋转Treap，性能不差，而且很容易实现区间操作，代码非常好写。区间操作非常类似线段树打懒标记和标记下传。通过平衡树我们把上述所有情况都可以$O(logn)$，算法的总体复杂度就是$O(nlogn)$。
对于FHQTreap讲解 推荐参考一下这篇文章。
评论 (0)