BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。
問題概要
二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。
長方形領域が与えられるので、その領域に含まれる格子点の個数を求めよ。
制約
- 座標値の絶対値
考えたこと
なので、想定解法は座標圧縮して二次元累積和だと思う。それによって の計算量で解ける。
ここでは、BIT on Wavelet Matrix で殴った。この構造を使うと、空間計算量も で抑えられる ( は最大値とする)。さらに一点加算も含めて、次のクエリに で答えられる。
- 一点加算
- 長方形領域の総和を取得
同様のことは、動的二次元 BIT でもできる。
コード
#include <bits/stdc++.h> using namespace std; // Bit Vector (for 64-bit non-negative integer) struct BitVector { // block: bit vector // count: the number of 1 within each block unsigned int n, zeros; vector<unsigned long long> block; vector<unsigned int> count; // constructor BitVector() {} BitVector(const unsigned int num) { resize(num); } void resize(const unsigned int num) { n = num; block.assign(((num + 1) >> 6) + 1, 0); count.assign(block.size(), 0); } // set val(0 or 1) onto i-th bit, get i-th bit of val(0 or 1) void set(const unsigned int i, const unsigned long long val = 1LL) { assert((i >> 6) < block.size()); block[i >> 6] |= (val << (i & 63)); } unsigned int get(const unsigned int i) const { assert((i >> 6) < block.size()); return (const unsigned int)(block[i >> 6] >> (i & 63)) & 1; } void build() { for (unsigned int i = 1; i < block.size(); i++) { count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]); } zeros = rank0(n); } // the number of 1 in [0, i) unsigned int rank1(const unsigned int i) const { assert((i >> 6) < count.size()); assert((i >> 6) < block.size()); return count[i >> 6] + __builtin_popcountll(block[i >> 6] & ((1ULL << (i & 63)) - 1ULL)); } // the number of 1 in [i, j) unsigned int rank1(const unsigned int i, const unsigned int j) const { return rank1(j) - rank1(i); } // the number of 0 in [0, i) unsigned int rank0(const unsigned int i) const { return i - rank1(i); } // the number of 0 in [i, j) unsigned int rank0(const unsigned int i, const unsigned int j) const { return rank0(j) - rank0(i); } // the number of 0 in [0, n) unsigned int rank0() const { return zeros; } }; // 2D queries template<class POS, class VAL> struct BITonWaveletMatrix { // inner data struct BIT { VAL UNITY_SUM = 0; int N; vector<VAL> dat; // [0, n) BIT() {} BIT(int n, VAL unity = 0) : UNITY_SUM(unity), N(n), dat(n, unity) { } void init(int n) { N = n; dat.assign(n, UNITY_SUM); } // a is 0-indexed void add(int a, VAL x) { for (int i = a; i < (int)dat.size(); i |= i + 1) dat[i] = dat[i] + x; } // [0, a), a is 0-indexed VAL sum(int a) { VAL res = UNITY_SUM; for (int i = a - 1; i >= 0; i = (i & (i + 1)) - 1) res = res + dat[i]; return res; } // [a, b), a and b are 0-indexed VAL sum(int a, int b) { return sum(b) - sum(a); } // debug void print() { for (int i = 0; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; using Point = pair<POS, POS>; int n, height; POS mi = 0; vector<BitVector> bv; vector<Point> ps; vector<POS> ys; vector<BIT> bit; // constructor (sigma: the number of characters) // add_point() cannot be used after build() BITonWaveletMatrix() {} BITonWaveletMatrix(const vector<Point> &vec) { for (auto [x, y] : vec) add_point(x, y); build(); } void add_point(POS x, POS y) { ps.emplace_back(x, y); ys.emplace_back(y); mi = min(mi, y); } int xid(POS x) const { return lower_bound(ps.begin(), ps.end(), Point(x, mi)) - ps.begin(); } int yid(POS y) const { return lower_bound(ys.begin(), ys.end(), y) - ys.begin(); } void build() { sort(ps.begin(), ps.end()); ps.erase(unique(ps.begin(), ps.end()), ps.end()); n = (int)ps.size(); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); vector<int> v(n), left(n), right(n), ord(n); int mv = 1; for (int i = 0; i < n; ++i) { v[i] = yid(ps[i].second); mv = max(mv, v[i]); } for (height = 1; mv != 0; mv >>= 1) ++height; iota(ord.begin(), ord.end(), 0); bv.resize(height, BitVector(n)); bit.assign(height + 1, BIT(n)); for (int h = height - 1; h >= 0; --h) { int l = 0, r = 0; for (int i = 0; i < n; ++i) { if ((v[ord[i]] >> h) & 1) { bv[h].set(i); right[r++] = ord[i]; } else { left[l++] = ord[i]; } } bv[h].build(); ord.swap(left); for (int i = 0; i < r; ++i) ord[i + l] = right[i]; } } // add void add(const POS x, const POS y, const VAL val) { int i = lower_bound(ps.begin(), ps.end(), Point(x, y)) - ps.begin(); int j = yid(y); for (int h = height - 1; h >= 0; --h) { int i0 = bv[h].rank0(i); if ((j >> h) & 1) { i += bv[h].rank0() - i0; } else { i = i0; } bit[h].add(i, val); } } // sum VAL inner_sum(int l, int r, const POS upper) { assert(0 <= l && r <= n); VAL res = 0; for (int h = height - 1; h >= 0; --h) { int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if ((upper >> h) & 1) { l += bv[h].rank0() - l0; r += bv[h].rank0() - r0; res += bit[h].sum(l0, r0); } else { l = l0; r = r0; } } return res; } VAL sum(const POS lx, const POS rx, const POS ly, const POS ry) { int l = xid(lx), r = xid(rx); return inner_sum(l, r, yid(ry)) - inner_sum(l, r, yid(ly)); } }; void AOJ_2426() { BITonWaveletMatrix<long long, long long> wm; int N, M; cin >> N >> M; vector<long long> x(N), y(N), lx(M), ly(M), rx(M), ry(M); for (int i = 0; i < N; ++i) { cin >> x[i] >> y[i]; wm.add_point(x[i], y[i]); } wm.build(); for (int i = 0; i < N; ++i) { wm.add(x[i], y[i], 1); } for (int q = 0; q < M; ++q) { cin >> lx[q] >> ly[q] >> rx[q] >> ry[q]; ++rx[q], ++ry[q]; cout << wm.sum(lx[q], rx[q], ly[q], ry[q]) << endl; } } int main() { AOJ_2426(); }