noshi91のメモ

データ構造のある風景

LISの計算について

LISは競プロでも低くない頻度で出現する題材です。

一般に知られている計算方法では単純な配列を用いてO(NlogN)でLISの計算が可能ですが、BITを用いることで同じ計算量でより直感的に(個人差あり)LISの計算が可能なのでそれについて少し書きます。

 

与えられた数列をAとします。

まずDP配列 B を用意し

・B_i =A_iを最後尾にしたLISの最大長さ

と定義します。

すると

・B_i =max( {B_k | 0<=k<i, A_k<A_i } ) + 1

と計算することができます。これは2次元クエリなので一般にNlog^2N掛かってしまいますが、B_iを計算する順番を工夫することによってもっと簡単に高速化が可能です。

すなわちBを0で初期化し、Aの値が小さい順にB_iを計算していきます。すると、条件のうち(A_k<A_i)が不要になります。何故なら、現在見ている値より大きい値を持つ場所はまだ計算されておらず、0で初期化されたままだからです。これを整理すると

・ある要素より左にある全ての要素の最大値の取得

・要素への値の代入

の2つの操作を行うことが出来れば良いことが分かります。ここで代入操作が常により大きい値への変更になることに着目すればセグ木ではなくBITで十分だと分かります。計算順に関して、A_j=A_kの場合ですが、広義単調増加なら添え字の小さい順、狭義単調増加なら添え字の大きい順に計算すればよいです。

これでめでたく、LISをO(NlogN)で計算することができました。

 

ーーーーーーーー以下この方法で解ける問題のネタバレを含みますーーーーーーーー

 

 

 

 

 

 

 

・第四回 ドワンゴからの挑戦状 本選B だんだん強く

 

上の方法でBITをそのまま使いまわしK周更新を行うと、各添え字についてその要素を最後尾に持つルール違反がK回以下のLISの長さが計算できます。K+1回ループを回して要素の小さい順に更新を繰り返せば終わりです。

 

 

・JOI '11 春合宿day4-2 Bookshelf

 

重み最大の増加列を求める問題に帰着されます。B_i=A_iを最後尾にしたLISの最大重みと定義すれば上記の方法で計算できます。

 

 

 

欠点として、全ての要素を前もって知ることができない場合はこの方法は使用できないというものがあります。

既出な気がするし誰でも思いつくので参考程度に