2019年9月17日火曜日

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

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

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

というテーブルを作っておけば、クエリ(QL,QR)(QL, QR)に対する答えはO(logN){\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

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

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


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

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