簡易化: 変数の固定
まずは人と座標を固定して考える． 時刻と座標の二つの単位があるので，一方に統一して判定式を作る． ここでは，時刻に注目した式で判定する． 人 \(i \in Q\) が座標 \(x\) を訪れた時点で 工事中であるのは， \(d_{i}+x \in [s,t)\) と同値． すなわち， \(d_{i} \in [s-x,t-x)\) と同値．
解法 0: Event sort
時刻毎にイベントを作る． 優先順位に注意する． 同じ時刻なら， (工事が終わる) > (工事が始まる) > (人が訪れる) の優先順位になる． それに応じて，タイプに番号を付ける．
- Type -1: Erase: 座標 \(x\) の工事が終わる
- Type 1: Add: 座標 \(x\) の工事が始まる
- Type 2: Visit: 人 \(i\) が座標 \(x\) を訪れる
あとはイベントを時刻でソートして実行する． 時刻 \(time\) のイベントを実行しているとき， \(time\) 未満のイベントは全て終わっている．
Type のイベントが起きたとき， 人 \(i\) に対する答えを求めたい． 時刻でイベントをソートしているから， \(i\) が訪れる以前の工事の処理(開始と終了)は全て実行済みである． よって，あとは工事されている座標全体のうち， 最小の値を取得すればよい． これは，工事中の座標を set で持っておけば良い．
解法 1: 答えの全探索
問われているのは (人 \(i) \mapsto \) (座標 \(x) = ans_{i}\) であるが，逆に \(x \mapsto i\) を求める． つまり，
座標 \(x\) を全探索したいので， \(\ (x, \cdots)\ \) の形でソートした配列を考える． \(x\) においてもっておきたい情報は \(s,t\) である． \(s-x, t-x\) は \(s,t\) があれば作れるので持っておく必要が無い．
\(x\) を全探索したら，対応する人 \(i\) を全て求めるが， それは \(d_{i} \in [s-x,t-x)\) と同値． \(\ (x,s,t)\ \) を知っている状態で，この様な \(d_{i}\) を求めるには \(d_{i}\) の set を持っておいて，binary search すれば良い．
注意: \(x\) が答えと決めた \(d_{i}\) は， 最初の工事で足を止めるため \(x\) より後ろが答えになる事はない． よって，\(d_{i}\) を set から削除しないと正しい答えが求まらない． このとき，iterator の更新に注意．削除したせいで iterator がずれるので， it = ds.erase(x); の様に書くのが正しい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
