考察
増加部分列では末尾が最大の要素になる。そのため、各長さについて「末尾をどこまで小さくできるか」が分かれば、値の上限を満たすかも判定できる。質問ごとに要素を除いてLISを求め直す代わりに、この最小末尾を共有することを考える。
質問で使うのは先頭からの区間(prefix)なので、右端が短い質問から処理すれば、配列の要素を一つずつ追加するだけでよい。各質問でLISを再計算すると最悪 かかるが、同じprefixまでの計算を使い回せる。
元の配列の添字は とする。先頭の 要素を処理した時点で、動的配列 tails を次の意味で持つ。
tails の添字は0始まりで、tails[j] は長さ の狭義単調増加部分列の最小末尾である。
- 存在する長さの分だけ要素を持つ。空のprefixでは
tails も空で、現在のLIS長は tails.size() に等しい。
- 長さが増えるほど最小末尾も狭義に増加するため、
tails は二分探索できる。
新しい値 を追加するときは、lower_bound(tails, A_i)、すなわち 以上の最初の要素の位置 を探す。その位置があれば tails[p] を に置き換え、末尾の次なら追加する。等しい値も置き換えるので、同じ値を二度選んで長さを増やすことはない。
例えば なら、更新は次のようになる。
では、値の上限 を持つ質問にはどう答えるか。長さ の部分列で全要素を 以下にできる条件は、tails[j] が 以下であることだ。最小末尾自体が 以下なら、その末尾を実現する増加部分列の全要素も上限を満たす。
tails は増加しているので、 以下の要素は先頭に連続して並ぶ。その個数を とすると、対応する長さは であり、最大長も となる。upper_bound(tails, X) が返す「 より大きい最初の位置」は、この個数 そのものである。最後に条件を満たす添字に1を足す代わりに、条件を満たす要素の個数を直接読むと考えると、添字と長さを混同しにくい。
先ほどの例では、 の tails=(2) で の答えは1。 の tails=(2,3) では、 なら位置1、 なら末尾の次の位置2が返り、答えはそれぞれ1、2になる。更新の lower_bound と質問の upper_bound は、等しい値の扱いが異なる。
具体的には、質問を右端 ごとのbucketへ入れ、値上限 と入力時の質問番号を保存する。tails を空で初期化し、 の順に次を行う。
- を
lower_bound で tails に反映する。
- の質問すべてに、
upper_bound(tails, X) の0始まりの位置を答える。
- 答えを元の質問番号の場所へ保存する。
最後に答えの配列を入力順に出力する。同じ右端を持つ質問はすべて、 を含む同じ状態で処理する。
典型の発動条件
offline prefix query
質問を入力順に処理する必要がなく、先頭からの区間の状態を一要素ずつ更新できるときに使う。右端ごとのbucketで処理すれば、質問のソートも不要になる。入力時の質問番号を持って答えの順序を戻す。
LIS tails invariant
同じ長さの増加部分列なら、末尾が小さいほど将来の値をつなげやすい。長さ別の最小末尾だけを残し、狭義増加では lower_bound で更新する。その状態が値上限にも答えられるかは、末尾と部分列全体の値の関係から確認する。
問題固有の要素
「全要素が 以下」という条件も、増加部分列では末尾一つで判定できる。値上限をDPの新しい次元にせず、最小末尾列の中で条件を満たす長さを二分探索すればよい。
別の問題へ持ち帰る視点は、標準のDPが保持する最適値から、追加された質問条件を直接判定できないかを調べることだ。
正当性
tails[j] を長さ の増加部分列の最小末尾とする。長さ の部分列から末尾を除くと、その末尾より小さい値で終わる長さ の部分列が得られるため、最小末尾も長さとともに狭義に増加する。
空のprefixでは不変条件を満たす。新しい値 の lower_bound の位置を とすると、 なら tails[p-1] は より小さく、それを実現する長さ の部分列に をつなげられる。 なら 単独を選べる。いずれも長さ の末尾を にできる。より短い長さの最小末尾はすでに より小さいので改善せず、より長い部分列を で終えるには、更新前に長さ 以上で末尾が 未満の部分列が必要だが、それは の定義に反する。従って位置 の置換または末尾への追加だけで不変条件を保つ。
値上限 を満たす長さ の増加部分列が存在すれば、その末尾以下である tails[j] も 以下である。逆に tails[j] が 以下なら、その最小末尾を実現する部分列の全要素が 以下になる。従って実現可能な長さは、tails の中の 以下の要素数を として であり、答えは である。upper_bound の0始まりの位置はこの個数に等しい。各質問をちょうど先頭の 要素を反映した直後に処理するので、求めるprefixに対する正しい答えを返す。
実装上の注意
tails は0始まりの動的配列とし、未到達の長さや番兵は入れない。更新位置が tails.size() なら追加し、それ以外なら置換する。
- 狭義増加の更新には、同値を置き換える
lower_bound を使う。質問は上限と等しい値も許すので upper_bound を使う。C++なら upper_bound(tails.begin(), tails.end(), X) - tails.begin() が答えであり、1を足したり引いたりしない。
- の質問には の更新後に答える。特に や、最後の要素を選んで答えが伸びる質問で処理順の誤りが現れる。
- 質問の処理順は右端の順へ変わるため、答えは元の質問番号で保存する。
復習の核
- 長さ別の最小末尾は、将来の延長だけでなく「全要素が上限以下か」の判定にも使える。
tails[j] は長さ 。答えは最後の添字ではなく、上限以下の末尾の個数で読む。
- 同値を伸ばさない更新は
lower_bound、同値を含めて数える質問は upper_bound。
計算量と制約
時間
要素、 質問。bucketの準備と出力は 、各要素の更新と各質問の二分探索はそれぞれ なので、全体は 。質問をソートする方法では別途 が必要になる。
空間
tails と元の配列に 、bucketと答えの配列に を使い、全体は 。
制約との対応
、 なので、質問ごとの再計算を避け、一要素・一質問あたり二分探索一回で処理する。 であり、 が保証されるため、公式入力の答えは必ず1以上になる。上限より大きい末尾がなければ、upper_bound は末尾の次を返し、答えは tails.size() になる。制限時間は2秒、メモリ制限は1024 MiB。
出典