\(O(N^2)\)LIS计算长度
直接套用dp方程
\(f_i=\max\limits_{0<j<i\ and\ A_i>A_j}\{f_j + 1\}\)
\(O(N\log N)\)LIS计算长度
二分做法
记\(f_i\)为长度最长为i的LIS结尾最小值,\(f_i\)单调递增.每次二分查找最后一个比\(A_i\)小的值即可
数据结构维护
观察方程, 我们扫描下标一维, 用权值线段树或树状数组维护值域一维(如果值域很大离散化即可),每次查询\(A_i\)(如果不写左闭右开是\(A_i-1\))前缀最大值,\(f_i\)存储在\(A_i\)的位置上即可.
LIS方案数统计
我们在维护最大值时维护一下区间内所有最大值的方案数,对其求和即可.这是一个区间分治信息,可以用上述数据结构解决.
最长不下降子序列
这个和上面同理