E – Roadwork 解説(AtCoder Beginner Contest 128)

2020年3月15日AtCoder競プロ, セグメント木, 区間, 更新, データ構造, set, imos法, 遅延評価セグメント木, イベントソート, 座標圧縮

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻 \(S_i−0.5\) から時刻 \(T_i−0.5\) まで座標 \(X_i\) が通れなくなる。
\(j\) 番目の人は時刻 \(D_j\) に座標 0 を出発し、速度 1 で正の方向へ歩き続ける。 通行止めとなっている地点に到達した場合には、そこで止まる。
Q 人それぞれが進む距離を求めよ。ただし止まらない場合は -1 を出力する。

制約

  • \(1 \leq N, Q \leq 2 \times 10^5\)
  • \(0 \leq S_i < T_i \leq 10^9\)
  • \(1 \leq X_i \leq 10^9\)
  • \(0 \leq D_1 < D_2 < … < D_Q \leq 10^9\)

考え方

単純にシミュレーションするのは難しそうですし、計算時間も間に合いません。

まずは \(i\) 番目の道路工事が \(j\) 番目の人に影響を与えるのはどのような場合かを考えてみましょう。

座標 \(X_i\) に到達するのは、\(D_j + X_i\) になります。全て整数であることに注意すると以下の式が成り立ちます。

\begin{align}
&S_i−0.5 \leq D_j + X_i \leq T_i−0.5 \\
&\Leftrightarrow S_i – X_i −0.5 \leq D_j \leq T_i – X_i −0.5 \\
&\Leftrightarrow S_i – X_i \leq D_j < T_i – X_i
\end{align}

つまり区間 \([S_i – X_i, T_i – X_i)\) に \(D_j\) があれば、人 \(j\) がその通行止めの影響を受ける可能性があります。

  • \([S_i – X_i, T_i – X_i)\) に \(D_j\) が存在すれば、人物 \(j\) は少なくとも \(X_i\) で止まる

影響を受ける人は1人とは限らないので以下のように言えるはずです。

  • \([S_i – X_i, T_i – X_i)\) に存在する \(D_j, D_{j+1}, D_{j+2}, …, D{k}\) に対応する人物 \(j, j+1, j+2, …, k\) が少なくとも \(X_i\) で止まる

注意としては、より手前側で通行止めがあった場合は、後半の通行止めの影響を受けない点です。つまり、より小さい \(X_k\) で同様の条件を満たせば、少なくとも \(X_k\) で止まるはずです。

以上からやりたいこととしては、

  • 「人物 \(j, j+1, j+2, …, k\) が少なくとも \(X_i\) で止まる」という区間の更新を N 回上手く行う

ということになります。

解法1:遅延評価セグメント木

想定解法ではありませんが、「区間更新・一点取得」のセグメント木で解くことができます。

区間の更新は遅延評価セグメント木で行うことができます。更新時は値を置き換えるのではなく、\(X_i\) の最小値を取るようにしましょう。

人物の番号を、セグメント木の葉に対応させましょう。「人物 \(l, l+1, l+2, …, r-1\) が少なくとも \(X_i\) で止まる」というのが分かったら、seg.update(l, r, X[i]) などと更新してやればよいです。

どこからどこまでの区間を更新すれば良いかは、二分探索で求めることができます。

解法2:イベントソート

公式解説にもある方法で、イベントソートと呼ばれる方法で解くこともできます。

イベントを時系列順にソートすることで、「ある時刻 t までにどのイベントが起きて、現在(時刻t)がどんな状態なのか」を時系列順にたどることができます。

今回で言えば2種類のイベントが考えられます。

  • 時刻 \(S_i – X_i\) からイベント \(i\) 開始。以降に出発した人は \(X_i\) で通行止め
  • 時刻 \(T_i – X_i\) にイベント \(i\) 終了。以降に出発した人は \(X_i\) で通行止めされない

時系列順にたどるので、現在時刻 t の状態として、

  • いま発生しているイベントの内容(具体的には \(X_i\) の値)

を set などで保持しておく必要があります。イベントの開始には「値の挿入」、イベントの終了には「値の削除」を行えば良いです。

全体のイメージとしては、時間という区間を圧縮した imos 法のような形です。