LIS メモ

数列A=a_1,a_2,...a_NのLISを求める

 

二分探索

dp[i]:=長さiの増加列の末尾の要素の最小値

ISの長さが長いほど末尾の要素は大きくなっていくので、このテーブルは単調増加になる

a_1から順にdpテーブル上を二分探索し、末尾の値を更新していく

更新時に、数列の位置ごとにdpテーブルのどの位置に入ったかをメモしておくことで、数列を後ろから見て復元ができる

狭義ISの場合はlower_bound,広義ISの場合はupper_boundで、はじめてa_i以上に(より大きく)なる位置を探し、その位置をa_iにする

オーダーはO(NlogN)

 

 

RMQ

dp[i]:=末尾がiであるようなISの長さの最大値

狭義ISの場合の更新はdp[a_i]=1+max(dp[x]|x<a_i) 

dpテーブルをセグ木で作り、maxの取得にRMQを使う

dpテーブル全体のmaxを見ることでLISの長さの取得ができる

座圧が必要

dpテーブルとは別にセグ木を持ち、更新に合わせて各nodeのmaxがどのindexに由来するかをメモしておくことで、RMQでmaxの添え字を特定できるようになる

→LISの後ろから、前回のmaxの位置より左側でのmax位置の取得を繰り返すことで復元ができる

オーダーはO(NlogN)