コンテンツにスキップ

座標圧縮

タグ「座標圧縮」の記事 5 件

DOJ Beginner Contest 13 C - Measures

ある標準錘の重さを NN 個の都市で量った記録があります。ii 番目の都市の 11 ポンドは UiU_i グレインで、その都市は標準錘を AiA_i ポンド(11 ポンド未満は切り捨て)と記録しました。標準錘の実際の重さは、グレインで表すと正の整数です。残った記録がすべて正しくありうるように、除く記録の最小個数を求める問題です(1≤N≤2000001 \le N \le 200000、1≤Ui≤100001 \le U_i \le 10000、0≤Ai≤1000000 \le A_i \le 100000)。

標準錘の重さを WW グレインとすると、記録 ii が正しいのは ⌊W/Ui⌋=Ai\lfloor W / U_i \rfloor = A_i、つまり

UiAi≤W<Ui(Ai+1)U_i A_i \le W < U_i (A_i + 1)

のときです。さらに W≥1W \ge 1 なので、記録 ii が正しくなる WW は半開区間 [max⁡(UiAi,1),Ui(Ai+1))[\max(U_i A_i, 1), U_i (A_i + 1)) です。Ui=1,Ai=0U_i = 1, A_i = 0 のときはこの区間は空で、その記録は必ず除くことになります。

WW を固定すると、残せる記録は WW を含む区間の個数です。よって、NN 個の区間が最も多く重なっている点での重なりの数を cc とすると、答えは N−cN - c です。

区間の端点は 10910^9 程度まで大きくなるので、端点を座標圧縮してからいもす法で各点の重なりの数を求めます。重なりの数が変わるのは区間の左端だけなので、左端と右端の座標だけ見れば十分です。計算量は O(Nlog⁡N)O(N \log N) です。

W≥1W \ge 1 の条件を区間の左端に入れておくのが大事です。左端を UiAiU_i A_i のままにして、座標 00 での重なりの数を最大値の候補から除くだけだと、Ai=0A_i = 0 の記録の区間 [0,Ui)[0, U_i) が数えられなくなります。例えば N=1N = 1、(U1,A1)=(4,0)(U_1, A_1) = (4, 0) では、W=1W = 1 なら記録が正しいので答えは 00 ですが、座標 00 を除くと 11 になってしまいます。

Python
import bisect
N = int(input())
lr = []
comp = []
for i in range(N):
u, a = map(int, input().split())
l = max(u * a, 1)
lr.append((l, u * (a + 1)))
comp.append(l)
comp.append(u * (a + 1))
comp = sorted(set(comp))
imos = [0] * len(comp)
for l, r in lr:
imos[bisect.bisect_left(comp, l)] += 1
imos[bisect.bisect_left(comp, r)] -= 1
for i in range(1, len(imos)):
imos[i] += imos[i - 1]
print(N - max(imos))

comp が座標圧縮した端点の座標で、imos[i] は累積和をとったあと、点 comp[i] を含む区間の個数になります。空の区間は、同じ位置に +1+1 と −1-1 が入るので打ち消し合います。

座標圧縮のリンク集

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

座標圧縮(座圧)は、値を「全体の中で何番目に小さいか」に置き換える手法です。値の大小関係だけが大事で、値そのものが 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
    • クエリを先読みして現れる値を座標圧縮し、値ごとの情報をセグメント木で管理しています。

AALC001 K - Multiset

はじめ NN 個の要素 A1,…,ANA_1, \dots, A_N をもつ整数の多重集合 SS に対して、次の 3 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5, 0≤Ai,x≤1090 \le A_i, x \le 10^9)。

  • 1 x:SS に xx を 1 個追加する。
  • 2 x:SS から xx を 1 個削除する(xx が含まれることは保証される)。
  • 3:SS の要素を昇順に並べた列を x1,…,xkx_1, \dots, x_k として、∑i=1kixi\sum_{i=1}^{k} i x_i を 998244353998244353 で割った余りを出力する。

クエリを先読みして、現れる値を座標圧縮します。値ごとに、その値の要素の「値の和 uu」と「(順位)×(値)の和 ww」を管理すると、答えは ww の総和です。同じ値の要素どうしは、どの順に並べても ∑ixi\sum i x_i は変わりません。そのため、同じ値の要素の中での順番は自由に決めてよいです。

値 xx を追加するとき、xx は同じ値の要素の中で先頭に入れることにします。すると、

  • xx 以上の値の要素(同じ値の要素も含む)は順位が 1 つずつ増えるので、それぞれの値について ww が uu だけ増えます。
  • 追加した要素の順位は「xx 未満の要素の個数 +1+ 1」なので、値 xx の uu に xx、ww に(順位)×x\times x を足します。

削除は逆で、同じ値の要素の中の先頭を取り除くことにします。xx 以上の値の ww から uu を引き、値 xx の uu から xx、ww から「xx 未満の要素の個数」×x\times x を引きます。ここでの順位は、全体の順位を 1 つ下げた後の値です。

「xx 以上の値すべての ww に c⋅uc \cdot u を足す」は区間への作用です。そのため、値ごとの (u,w)(u, w) を遅延評価セグメント木で管理します。作用 cc は (u,w)↦(u,w+cu)(u, w) \mapsto (u, w + c u) で、合成は和です。xx 未満の要素の個数は、値ごとの個数を持つ別のセグメント木で求めます。

全体の計算量は O((N+Q)log⁡(N+Q))O((N + Q) \log (N + Q)) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
#include "shogo-library/data_structures/segtree.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/utility/compress.hpp"
using mint = modint998244353;
struct AALC0001K {
struct S {
mint u, v;
S() : u{}, v{} {}
};
using F = mint;
static S op(const S &a, const S &b) {
S res;
res.u = a.u + b.u;
res.v = a.v + b.v;
return res;
}
static S e() { return S(); }
static S mapping(const F &f, const S &x) {
S res;
res.u = x.u;
res.v = x.u * f + x.v;
return res;
}
static F composition(const F &f, const F &g) { return f + g; }
static F id() { return 0; }
};
void solve() {
LL(N, Q);
VL(A, N);
Compress<ll> cp;
for (ll a : A)
cp.add(a);
val<2> query;
query.reserve(Q);
rep(Q) {
LL(q);
if (q <= 2) {
LL(x);
query.push_back({q, x});
cp.add(x);
} else {
query.push_back({q, 0});
}
}
cp.build();
RSumQ<ll> seg0(cp.size());
LazySegTree<AALC0001K> seg1(cp.size());
for (ll a : A) {
ll k = cp.id(a);
seg1.apply(k, cp.size(), 1);
auto g = seg1.get(k);
ll f = seg0.prod(0, k) + 1;
g.u += a;
g.v += f * a;
seg1.set(k, g);
seg0.apply(k, 1);
}
for (auto [q, x] : query) {
if (q == 1) {
ll k = cp.id(x);
seg1.apply(k, cp.size(), 1);
auto g = seg1.get(k);
ll f = seg0.prod(0, k) + 1;
g.u += x;
g.v += f * x;
seg1.set(k, g);
seg0.apply(k, 1);
} else if (q == 2) {
ll k = cp.id(x);
seg1.apply(k, cp.size(), -1);
auto g = seg1.get(k);
ll f = seg0.prod(0, k);
g.u -= x;
g.v -= f * x;
seg1.set(k, g);
seg0.apply(k, -1);
} else {
print(seg1.all_prod().v);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

コードでは ww を v という名前にしています。座標圧縮には Compress を使い、値を add で登録して build した後、cp.id(x) で値 xx の番号を得ます。seg0 は値ごとの個数を持つ区間和のセグメント木で、apply(k, c) は kk 番目の要素に cc を足す操作です。seg1 は値ごとの (u,w)(u, w) を持つ遅延評価セグメント木で、構造体には要素の型 S・作用の型 F と、op, e, mapping, composition, id をまとめています(ACL の lazy_segtree と同じ構成です)。初期の NN 個の要素も、追加クエリと同じ手順で 1 個ずつ入れています。

使用ライブラリ:cpp_include@397a51d

AALC001 J - Long Binary String

長さ 101810^{18} の 0, 1 からなる文字列 SS があり、はじめはすべて 0 です。次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤Q≤2×1051 \le Q \le 2 \times 10^5)。

  • 1 l r:Sl,…,SrS_l, \dots, S_r を反転する。
  • 2 l r:Sl,…,SrS_l, \dots, S_r に含まれる 1 の個数を出力する。

クエリを先読みして座標圧縮します。区間を 0 始まりの半開区間 [l−1,r)[l - 1, r) で表し、すべてのクエリの端点 l−1l - 1, rr を集めてソートし、重複を除いたものを v0<v1<⋯<vm−1v_0 < v_1 < \dots < v_{m-1} とします。すると、どのクエリの区間も小区間 [vj−1,vj)[v_{j-1}, v_j) をいくつか並べたものになります。また、各小区間の中の文字はつねにすべて同じように反転されます。

そこで、小区間 [vj−1,vj)[v_{j-1}, v_j) を 1 つの要素とする遅延評価セグメント木を作ります。各ノードには担当範囲の 0 の個数と 1 の個数を持たせます。はじめは 0 の個数が小区間の長さ vj−vj−1v_j - v_{j-1} で、1 の個数は 00 です。反転はこの 2 つを入れ替える作用で、2 回反転すると元に戻るので、作用の合成は XOR です。

全体の計算量は O(Qlog⁡Q)O(Q \log Q) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
#include "shogo-library/utility/compress.hpp"
void solve() {
LL(Q);
VAL(qlr, Q, 3);
Compress<ll> cp;
for (auto &[q, l, r] : qlr) {
l--;
cp.add(l);
cp.add(r);
}
cp.build();
using A = acted_monoid::Rearrange<monoid::Sum<ll>, 2>;
vec<A::S> init;
init.reserve(cp.size() - 1);
rep(i, 1, cp.size()) {
init.push_back({cp[i] - cp[i - 1], 0});
}
LazySegTree<A> seg(init);
for (auto [q, l, r] : qlr) {
if (q == 1) {
seg.apply(cp.id(l), cp.id(r), A::swap(0, 1));
} else {
print(seg.prod(cp.id(l), cp.id(r))[1]);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

VAL(qlr, Q, 3) で、クエリを std::array<ll, 3> の配列として読み込んでいます。座標圧縮には Compress を使い、端点を add で登録して build した後、cp[i] で viv_i、cp.id(x) で値 xx の番号を得ます。セグメント木の jj 番目の要素は小区間 [vj,vj+1)[v_j, v_{j+1}) なので、半開区間 [l−1,r)[l - 1, r) は要素の番号の範囲 [id(l−1),id(r))[\mathrm{id}(l - 1), \mathrm{id}(r)) に対応します。

acted_monoid::Rearrange<monoid::Sum<ll>, 2> は、和のモノイドを 2 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドです。成分 0 が 0 の個数、成分 1 が 1 の個数で、A::swap(0, 1) が反転の作用です。これを LazySegTree に渡しています。

使用ライブラリ:cpp_include@397a51d

SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R

長さ nn の数列 aa と整数 L,RL, R が与えられます。連続する部分列のうち、総和が LL 以上 RR 以下のものの個数を求める問題です(n≤105n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、−1014≤L≤R≤1014-10^{14} \le L \le R \le 10^{14})。aia_i は負になることもあります。

累積和を S0=0S_0 = 0、Sj=a1+⋯+ajS_j = a_1 + \cdots + a_j とすると、区間 [i+1,j][i + 1, j] の総和は Sj−SiS_j - S_i です。条件 L≤Sj−Si≤RL \le S_j - S_i \le R を SiS_i について書き直すと

Sj−R≤Si≤Sj−LS_j - R \le S_i \le S_j - L

です。したがって、各 jj について「i<ji < j で SiS_i が [Sj−R,Sj−L][S_j - R, S_j - L] に入るものの個数」を足し合わせれば答えになります。

aia_i が負になることもあるので SS は単調ではなく、しゃくとり法は使えません。そこで j=1,2,…,nj = 1, 2, \ldots, n の順に見ていき、それまでに出てきた SiS_i を、値ごとの個数として管理します。必要な操作は次の 2 つです。

  • SjS_j を 1 個追加する
  • 値が [Sj−R,Sj−L][S_j - R, S_j - L] の範囲にある SiS_i の個数を数える

SS の値は最大 101410^{14} 程度と大きいので、S0,…,SnS_0, \ldots, S_n を座標圧縮して添字にし、区間和を求めるセグメント木(または BIT)で管理します。値の範囲 [Sj−R,Sj−L][S_j - R, S_j - L] は、圧縮後の添字では二分探索で求まります。全体で O(nlog⁡n)O(n \log n) です。

C++(セグメント木)
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
void solve() {
LL(N, L, R);
VL(A, N);
ll t = 0;
sl s;
s.insert(t);
for (ll a : A) {
t += a;
s.insert(t);
}
vl v(all(s));
RSumQ<ll> seg(v.size());
ll ans = 0;
t = 0;
seg.apply(bisect_left(v, t), 1);
for (ll a : A) {
t += a;
ans += seg.prod(bisect_left(v, t - R), bisect_right(v, t - L));
seg.apply(bisect_left(v, t), 1);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

前半では累積和の値を std::set に入れ、ソート済みで重複のない v にしています(座標圧縮)。値 xx の添字は bisect_left(v, x) です。

後半では t が SjS_j で、seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)) が「値が [Sj−R,Sj−L][S_j - R, S_j - L] にある SiS_i の個数」です。数えてから seg.apply(..., 1) で SjS_j を追加するので、i<ji < j のものだけが数えられます。RSumQ は区間和のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

Python(BIT)
from bisect import bisect_left, bisect_right
from itertools import accumulate
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
S = [0, *accumulate(A)]
v = sorted(set(S))
M = len(v)
bit = [0] * (M + 1)
def add(i):
i += 1
while i <= M:
bit[i] += 1
i += i & -i
def count(i):
res = 0
while i:
res += bit[i]
i -= i & -i
return res
ans = 0
add(bisect_left(v, 0))
for t in S[1:]:
ans += count(bisect_right(v, t - L)) - count(bisect_left(v, t - R))
add(bisect_left(v, t))
print(ans)

C++ 版と同じ処理を BIT で書いています。count(i) は添字が ii 未満の個数なので、2 つの差が範囲内の個数になります。