UTPC 2012 H - 区間スケジューリングクエリ

• 問題
• AC

$R[k][t] :=$ 時刻$t$以降に最短で仕事を$2^k$個こなすときの終了時刻

というテーブルを作っておけば、クエリ$(QL, QR)$に対する答えは${\mathcal O}(\log N)$で求まる:

result := 0
for k from 16 downto 0
    if R[k][QL] <= QR
        result += 2^k
        QL := R[k][QL]
return result

ただし、このままでは時刻の範囲が大きすぎるので$IL_i, IR_i, QL_i, QR_i$に現れる時刻をまとめて座標圧縮しておく。

また、$R[0][t]$を初期化するために、時刻$t$以降に最初にこなすべき仕事（の終了時刻）を求めてなくてはならないが、$(IL_i, IR_i)$を終了時刻の昇順でソートしておいて順に処理していけばよい。

---

$R[k][x] :=$ 仕事$x$を終えた後に最短で仕事を$2^k$個こなすときの最後の仕事

という感じで仕事ベースでテーブルを作っておけば座標圧縮しなくても良いらしい。なるほど……