LIS
投稿者：CarpDay.icon
1. LISの概要
最長増加部分列問題．Longest Increasing Subsequenceの略．
数列 $ a_1, a_2, ..., a_nから，狭義増加列（前後が等しいのはNG）を作る．
部分列の長さは最長でいくつ？
参考：
2. 長さiのLISの最後尾数の最小値DP版（Python）
上の参考ページでのやり方．実装方法も2種類ある．
(1) リストの要素を追加するタイプ
code: python
from bisect import bisect_left
n = int(input())
#dpi: 長さ i のLISの最後の数のうち，最も小さな値 ans = 0
for x in a:
dp.append(x)
else:
idx = bisect_left(dp, x) # dpidx-1 < x <= dpidx print(len(dp) - 1)
(2) リストを最大数だけ確保しておくタイプ
code: python
from bisect import bisect_left
N = int(input())
INF = float('inf')
for a in A:
idx = bisect_left(dp, a)
# print(dp)
print(max(i for i in range(N + 1) if dpi < INF)) 2. 最後尾数がiであるLISの長さDP版（Python）
DPの途中段階におけるLISが獲得しやすいDP
セグメント木を使う．
格納する値が要素数より大きい場合は，座標圧縮が必要．
code: python
# 座標圧縮. comp: 圧縮後の配列, inve = i: 元の要素 def compress(a, idx=0):
sorted_a = sorted(list(set(a)))
inv = {e: i for i, e in enumerate(sorted_a, start=idx)}
cmp_a = [inve for e in a] return cmp_a, inv
from atcoder.segtree import SegTree
INF = float('inf')
op, e = max, -INF # 区間演算が最大値のとき．
n = int(input())
a, _ = compress(a, idx=1) # 座標圧縮（1-index)
# dpi: 最後の要素が i であるLISの長さ st = SegTree(op, e, -INF * (n + 1)) # dp = -INF * (n + 1) for aa in a:
st.set(aa, st.prod(0, aa) + 1) # dpaa = max(dp0:aa) + 1 print(st.all_prod())