(L, R) = (3,5), (7,8), (12,13), (4,10), (2,7) ↓ X = 3 4 5 7 8 12 13 4 5 6 7 8 9 10 2 3 4 5 6 7 (3 4 5 6 7 8 9 10) の、長さ8のLISが取れ、これが最長
LISをそのまま求める方法から情報を圧縮することを考える。(遅延評価セグ木でも解けるらしい)
一般的なLISは次のDPによって求められる。
例で構築した X をもとにこれをおこなっていくと、
DP 初期状態 [0] (3, 5) [0 3 4 5] ~~~~~ (7, 8) [0 3 4 5 7 8] ~~~ (12,13) [0 3 4 5 7 8 12 13] ~~~~~ (4, 10) [0 3 4 5 6 7 8 9 10] ~~~~~~~~~~~~~~~~ (2, 7) [0 2 3 4 5 6 7 9 10] ~~~~~~~~~~~~
となる。性質上、1ずつ増加する部分が非常に多い。
実際は制約が L,R≤109 のため、DP配列が 109 の長さになりえて、当然このままでは無理。
そこで、1ずつ増加する部分は省略し、それが途切れる右端部分 r と、その位置 i を保持することを考える。
このような r は、たかだか N 個に収まる。
実装上は、r は順番を保ったまま追加・削除ができる平衡二分探索木やSortedSetのようなデータ構造で管理し、 r→i は辞書で関連付けることにする。
旧DP DP r:i 初期状態 [0] {0:0} (3, 5) [0 3 4 5] {0:0 5:3} ~~~~~ (7, 8) [0 3 4 5 7 8] {0:0 5:3 8:5} ~~~ (12,13) [0 3 4 5 7 8 12 13] {0:0 5:3 8:5 13:7} ~~~~~ (4, 10) [0 3 4 5 6 7 8 9 10] {0:0 10:8} ~~~~~~~~~~~~~~~~ (2, 7) [0 2 3 4 5 6 7 9 10] {0:0 7:6 10:8} ~~~~~~~~~~~~
説明上、DPの1つの {r:i} を「r の区間」と呼ぶことにする。
たとえば上例の最下段のDPで、「7の区間」は {7:6} 、旧DPで (2,3,4,5,6,7) の部分に相当する。
重要な事実として、(L,R) で更新されるたびに、旧DP上にはどこかしらで L,L+1,...,R の並びができる。
元来のLISのDPの更新方法「DP配列上で、自身未満で一番大きい要素の次に、自身を上書きまたは追加する」という更新方法からしても分かるとおり、
更新後のDP配列には必ず、直近に更新した値が存在する。
(元から同じ数字が存在していて、実質的には更新されていない、ということもあり得るが、存在はする)
(L,R) をまとめて更新する際でもそれが連鎖的に起きるため(L+1 を更新するときには必ず L が存在し、かつそれが L+1 未満で一番大きい要素)、L,L+1,...,R の並びは必ず作られる。
よって、(L,R) をまとめて更新する際には、「どの位置から L がスタートするか?」が分かればよい。
ただその際、上書きされて不要になる区間があったりするので、更新パターンを考える。
具体的には以下の手順で更新できる。更新作業を行う関数を f(L,R) とする。
まず、追加しようとしている並びの左端 L の位置を知るため、DPから以下の値を得る。
追加しようとしている(L,R) = (5, 8) 旧DP DP [0 2 3 4 5 6 7 9 10] {0:0 7:6 10:8} → r1 = 0 i1 = 0 r2 = 7 i2 = 6 l2 = 2
最終的なDPのうち、最大の r に対応する i が答えとなる。
r の追加・削除はそれぞれたかだか N 回までしか行われず、探索も追加・削除毎に最大2回、計 4N 回までなので、 これらの操作1回を O(logN) や O(√N) で行えれば、全体で O(NlogN) や O(N√N) となり実行制限時間に間に合う。
本問題は、ナイーブなLISのDPから情報を圧縮したが、
「実際に更新によってどのようになるか」は
いきなり圧縮後の状態だけで考えてもイメージしにくく、
圧縮前の方が理解しやすかった。
問題にもよるが、着実に考察を進めるには2つを並べて行き来することが肝要だね。