(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 \le 10^9$ のため、DP配列が $10^9$ の長さになりえて、当然このままでは無理。
そこで、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(\log{N})$ や $O(\sqrt{N})$ で行えれば、全体で $O(N\log{N})$ や $O(N\sqrt{N})$ となり実行制限時間に間に合う。
本問題は、ナイーブなLISのDPから情報を圧縮したが、
「実際に更新によってどのようになるか」は
いきなり圧縮後の状態だけで考えてもイメージしにくく、
圧縮前の方が理解しやすかった。
問題にもよるが、着実に考察を進めるには2つを並べて行き来することが肝要だね。