コンテンツにスキップ

座標圧縮のリンク集

座標圧縮について、参考になる記事や資料をまとめました。

座標圧縮(座圧)は、値を「全体の中で何番目に小さいか」に置き換える手法です。値の大小関係だけが大事で、値そのものが 10910^9 のように大きいときに、00 から N−1N - 1 までの添字に直して配列で扱えるようにします。同じ値には同じ番号を付けます。

C++ では、値をコピーしてソートし、std::unique と erase で重複を除いたあと、std::lower_bound で各値の番号を求めます。Python では sorted(set(A)) で重複のない昇順の列を作り、辞書で値から番号を引くか、bisect_left で番号を求めます。どちらも計算量は O(Nlog⁡N)O(N \log N) です。

よく使うのは、次のような場面です。

  • データ構造に載せる:値を添字にして BIT やセグメント木に載せるとき、値を圧縮して大きさを O(N)O(N) に抑えます。後から来るクエリの値も含めて圧縮するため、クエリを先読みすることが多いです。転倒数を求めるときも、値が大きければまず圧縮します。
  • 区間を扱う:区間の端点だけを集めて圧縮すると、数直線が「端点から次の端点まで」の小区間の並びになり、どの区間も小区間をいくつか並べたものになります。区間を半開区間 [l,r)[l, r) で表して端点 l,rl, r を集めると、扱いが簡単です。閉区間 [l,r][l, r] なら ll と r+1r + 1 を集めます。小区間の長さは、圧縮前の値の差で求めます。いもす法と組み合わせることもよくあります。
  • 2 次元のグリッド:x 座標と y 座標をそれぞれ別に圧縮して、小さなグリッドに直します。長方形や線分で区切られた領域を扱うときは、端点だけを残すと隙間が消えてしまうことがあり、端点の隣の座標も残す必要があります。
  • 座標圧縮 (座圧)(けんちょんの競プロ精進記録)
    • 「全体の中で何番目に小さいか」という定義から始めて、C++(ソート、unique と erase、lower_bound)と Python(sorted(set(A)) と辞書)の実装、例題の ABC036 C と ABC113 C、発展として 2 次元の点の座標圧縮(ABC213 C)を説明しています。初心者向けです。
  • 座標圧縮の解説(1次元から2次元の圧縮まで)(アルゴリズムロジック)
    • 1 次元の座標圧縮の手順と C++ の実装から、線分や長方形を扱う 2 次元の座標圧縮に進みます。端点だけでなく「一つ隣」の座標も残さないと隙間が消えてしまう理由を、圧縮の前後の図で説明しているのが特徴です。例題は AOJ DSL_4_A(長方形の面積の和)で、座標圧縮と 2 次元のいもす法で解いています。練習問題の一覧もあります。
    • 2.4 節のコードは for (T d = 0; d < 1; d++) になっていて、d = 0 しか回らないので、説明している「一つ隣の座標」が追加されません。最後の DSL_4_A のコードのように d <= 1 にしてください。
  • 座標圧縮(北海道大学 HCPC、PDF)
    • 2017 年の勉強会のスライドです。1 次元(ABC036 C)のあと、蟻本の「領域の個数」を例に、線分の端点だけを残すと誤る例を示して、端点の隣に余白の座標を足す方法を図で説明しています。応用として AOJ 2426 Treasure Hunt(座標圧縮と 2 次元の累積和)も扱っています。
    • スライドにコードはなく、GitHub へのリンクは切れています。コードは今はこちらにあります。スライド自身に、コードは verify していないと書かれています。
  • 座標圧縮に関する解説と練習問題(Baby Stepsなブログ)
    • 端点とその隣の座標を登録する圧縮の関数と、それを使った 3 問の C++ の解答です。AOJ DSL_4_A(2 次元のいもす法)、JOI 2008 本選「ペンキの色」(領域の個数を BFS で数える)、JOI 2013 予選「魚の生息範囲」(3 次元)を扱っています。説明は短く、コードが中心です。
  • 座標圧縮について勉強した java(バイトの競プロメモ)
    • 壁で区切られたグリッドを、まず x 方向だけ圧縮する様子を図で示しています。長方形の右端を半開区間の端として持てば、端点だけを残しても領域が小区間の並びとして正しく残ることが、具体的な数で分かります。両端の座標を入れ忘れると外側の余白が消えることにも触れています。コードは Java の断片です。
  • 転倒数を Binary Indexed Tree(BIT)で求める(embermaverick05、Qiita)
    • 転倒数を BIT で求める入門記事で、最後に値が 10910^9 まである場合に、sorted(set(A)) から作った辞書で値を圧縮してから BIT に載せる方法を説明しています。コードは Python です。
  • 平面走査について(Shirotsume、Qiita)
    • 転倒数を例に、片方の座標の順に処理しながら、もう片方の座標を BIT で数える平面走査の考え方を一般化して説明しています。座標圧縮そのものの解説ではありませんが、クエリを先読みして圧縮し、データ構造に載せるオフライン処理の考え方が分かります。コードはなく、数式と文章で説明しています。

AtCoder Library(ACL)に座標圧縮の機能はありません。

  • std::unique(cpprefjp)
    • std::unique は隣り合う重複を除いた要素を先頭に集めるだけで、要素数は減らないこと、実際に消すには戻り値を使って erase する必要があることが書かれています。隣り合う重複しか消さないので、先にソートが必要なことも例で分かります。
  • misc/compress.hpp(Nyaan’s Library)
    • 座標圧縮の構造体の C++ の実装です。説明の文章はなく、コードだけのページです。値の番号を求める get(x) は、x が登録されていなくても「xx 以上の最初の位置」を返すので、区間の端を求めるのにも使えます。
  • other/compress.hpp(Luzhiled’s Library)
    • 値を add で登録してから build で整える形の C++ の実装で、こちらもコードだけのページです。コンストラクタで値を渡しても build は呼ばれないので、番号を求める前に必ず build を呼んでください。

座標圧縮そのものを扱う講座はありませんが、座標圧縮を使う講座があります。

  • Wavelet Matrix(発展)
    • 6 章「2 次元点群に対する矩形処理」で、点の座標を圧縮して 00 から N−1N - 1 に直してから Wavelet Matrix に載せています。点の追加・削除がある問題では、クエリをすべて先読みしてから座標圧縮する方法も説明しています。難易度の高い講座です。
  • 区間クエリのためのモノイド設計
    • 8.1 節「転倒数」の補足で、値を添字にするときは座標圧縮してセグメント木の大きさを O(N)O(N) に抑えればよい、と触れています。

日本語版・英語版の Wikipedia と cp-algorithms には、座標圧縮の記事も節もありません。

  • Custom Comparators and Coordinate Compression(USACO Guide、英語)
    • 前半はソートの比較関数の話で、後半が座標圧縮です。2 次元の点の座標をソートした順位に置き換える例(USACO 2020 Dec Silver「Rectangular Pasture」)と、長さ 10910^9 の配列への区間加算と区間和を、端点を集めて圧縮し、圧縮前の値の差を小区間の長さとして使って解く例(Codeforces Gym 102951 D)があります。コードは C++・Java・Python から選べます。
    • 1 つ目の例のコードは、ソートした順に番号を振るだけで、重複を除いていません。この問題では座標がすべて異なることが保証されているので正しく動きますが、重複がある問題にそのまま使うと誤ります。
  • Spoj Problem: Election Posters(Codeforces、英語)
    • 区間を塗り重ねる問題についての質問スレッドです。端点だけを圧縮すると、間にある隙間が消えて答えが変わってしまう反例がコメントで示されていて、端点の扱いの落とし穴の実例になっています。
  • ABC188 D - Snuke Prime:料金が変わる日だけを取り出して(座標圧縮して)、いもす法で各期間の料金を求めます。
  • ABC221 D - Online games:ログイン人数が変わる日だけを取り出し、人数が同じ期間の日数を数えます。
  • ABC231 F - Jealous Two:片方の嬉しさの順に処理しながら、もう片方の嬉しさを圧縮して BIT で数えます。
  • AOJ DSL_4_A - Union of Rectangles:長方形の面積の和を、座標圧縮と 2 次元のいもす法で求めます。上のアルゴリズムロジックの記事が解説です。
  • ABC168 F - . (Single Dot):線分の端点で座標を圧縮してグリッドにし、牛のいる領域を BFS で探索して面積を足し合わせます。領域が外まで広がっていれば INF です。
  • SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R
    • 最大 101410^{14} 程度になる累積和の値を座標圧縮し、BIT(セグメント木)で個数を数えています。
  • AALC001 J - Long Binary String
    • クエリを先読みして区間の端点を座標圧縮し、長さ 10910^9 の文字列を小区間の並びに直して、セグメント木で反転を処理しています。
  • AALC001 K - Multiset
    • クエリを先読みして現れる値を座標圧縮し、値ごとの情報をセグメント木で管理しています。