2020年5月19日その他二次元, 座標圧縮

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。

仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。

例:\(0\) ~ \(10^9\) の数直線はメモリにのらない

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

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻 \(S_i−0.5\) から時刻 \(T_i−0.5\) まで座標 \(X_i\) ...