权值树状数组优化LIS问题。

LIS的权值树状数组$O(n\log n)$做法

可能需要的前置知识：

• $O(n^2)$的dp做法。
• 树状数组的概念，更新和查找前缀的操作。
• 听说过权值线段树/权值树状数组这种思想/操作。
• 离散化（本题还用不到）

对于传统的LIS问题，我们可以设$dp[i]$表示以第$i$个元素结尾且单增的子序列组成的集合中，序列最长的长度。考虑其能由哪些状态转移过来，容易发现，$dp[1...n - 1]$中有一部分可以更新$dp[i]$的值，我们的状态转移方程是：$dp[i] = max(dp[j] + 1)$，其中$\ 1 \leq j < i$且$a[j] < a[i]$ 。暴力每次$O(n)$的转移消耗无法应对$10^5$这样的数据范围，这个时候我们可以一个很自然的想法是想办法加速转移过程。

我们先想一下为啥刚才我们一下子没想到很快的优化方法，原因在于，能够转移到$dp[i]$状态的其他状态，是前缀，又不完全是前缀。$1\leq j < i$表明其确实是前缀的一部分，但是$a[j] < a[i]$的限制似乎使得我们必须暴力甄别出到底哪些$dp[j]$能够更新$dp[i]$。我们的希望是：如果$a[j] < a[i]$和$1\leq j <i$能够共同综合出一个新的“顺序”，同时满足这两个条件的元素是一个“前缀”就好了。这个时候，如果之前接触过“权值线段树/权值树状数组（值域线段树/值域树状数组）”（即把值作为下标，把值出现的次数作为该下标处存储的内容，即权值，或者你也可以存一些其他你关心的内容，根据题目不同而不同）这个概念的话，可能会想到这个玩意儿可以同时按照“顺序”和“大小”两个限制去维护元素集的属性。做法是，往数据结构中插入元素的时候，不是按照这个元素在原始数组中的下标去插入，而是这个元素的值是多少我们就把它插到哪个位置。这样的话，我们按照原始数组顺序遍历元素的时候，先查一下数据结构中比当前元素小的部分，就能查到比它小还比它靠前的元素的一些属性，然后把当前元素再插入到数据结构中，以此来维护数据结构。（以元素大小为数据结构中的“下标”）基于权值使用数据结构的话，一般要考虑值域过大空间不足的情况，遇到这种情况可能要做离散化。