Wavelet Matrix の prev_value や next_value が使える問題！
問題概要
サイズ の数列
が与えられる。次の
個のクエリに答えよ。
が与えられるので、数列の区間
の値のうち、
との差の最小値を答えよ。
制約
考えたこと
Wavelet Matrix の関数 prev_value() と next_value() がジャストヒットする。ただし、Wavelet Matrix に登録する各値が負の場合には対応していない実装をしているので、正になるように下駄を履かせることとした。
計算量は となる。
コード
#include <bits/stdc++.h> using namespace std; // Bit Vector struct BitRank { // block: bit vector // count: the number of 1 within each block vector<unsigned long long> block; vector<unsigned int> count; // constructor BitRank() {} void resize(const unsigned int num) { block.resize(((num + 1) >> 6) + 1, 0); count.resize(block.size(), 0); } // set val(0 or 1) onto i-th bit void set(const unsigned int i, const unsigned long long val) { block[i >> 6] |= (val << (i & 63)); } void build() { for (unsigned int i = 1; i < block.size(); i++) { count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]); } } // the number of 1 in [0, i) unsigned int rank1(const unsigned int i) const { 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); } }; // Wavelet Matrix (must vec[i] >= 0) template<class T> struct WaveletMatrix { // inner data int height; vector<BitRank> bv; vector<int> pos; vector<vector<long long>> rui; // constructor (sigma: the number of characters) WaveletMatrix() {} WaveletMatrix(vector<T> vec) : WaveletMatrix(vec, *max_element(vec.begin(), vec.end()) + 1) {} WaveletMatrix(vector<T> vec, T sigma) { init(vec, sigma); } void init(vector<T> &vec, T sigma) { height = (sigma == 1) ? 1 : (64 - __builtin_clzll(sigma - 1)); bv.resize(height), pos.resize(height); vector<T> A = vec; rui.resize(height + 1); for (int i = 0; i < height; ++i) { bv[i].resize(vec.size()); for (int j = 0; j < vec.size(); ++j) { bv[i].set(j, get(vec[j], height - i - 1)); } bv[i].build(); auto it = stable_partition(vec.begin(), vec.end(), [&](int c) { return !get(c, height - i - 1); }); pos[i] = it - vec.begin(); } for (int i = 0; i <= height; ++i) { rui[i].resize((int)A.size() + 1); for (int j = 1; j <= (int)A.size(); ++j) { rui[i][j] = rui[i][j - 1] + A[j - 1]; } if (i == height) break; stable_partition(A.begin(), A.end(), [&](int c) { return !get(c, height - i - 1); }); } } // the i-th bit of "val" (0 or 1) int get(const T val, const int i) { return val >> i & 1; } // the number of "val" in [l, r) int rank(const T val, const int l, const int r) { return rank(val, r) - rank(val, l); } // the number of "val" in [0, i) int rank(T val, int i) { int p = 0; for (int j = 0; j < height; ++j) { if (get(val, height - j - 1)) { p = pos[j] + bv[j].rank1(p); i = pos[j] + bv[j].rank1(i); } else { p = bv[j].rank0(p); i = bv[j].rank0(i); } } return i - p; } // the k-th (0-indexed) smallest value in [l, r) T k_th_smallest(int k, int l, int r) { T res = 0; for (int i = 0; i < height; ++i) { const int j = bv[i].rank0(l, r); if (j > k){ l = bv[i].rank0(l); r = bv[i].rank0(r); } else { l = pos[i] + bv[i].rank1(l); r = pos[i] + bv[i].rank1(r); k -= j; res |= (1LL << (height - i - 1)); } } return res; } // the k-th (0-indexed) largest value in [l, r) T k_th_largest(int k, int l, int r) { return k_th_smallest(r - l - k - 1, l, r); } // the sum of the top-k sum in [l, r) T top_k_sum(int k, int l, int r) { if (l == r) return 0; T res = 0, val = 0; for (int i = 0; i < height; ++i) { const int j = bv[i].rank0(l, r); if (j > k) { l = bv[i].rank0(l); r = bv[i].rank0(r); } else { int l2 = bv[i].rank0(l); int r2 = bv[i].rank0(r); res += rui[i + 1][r2] - rui[i + 1][l2]; l = pos[i] + bv[i].rank1(l); r = pos[i] + bv[i].rank1(r); k -= j; val |= (1LL << (height - i - 1)); } } res += (long long)val * k; return res; } // the number of value between [loewr, upper) in [l, r) int range_freq(const int i, const int j, const T lower, const T upper, const int l, const int r, const int x) { if (i == j || r <= lower || upper <= l) return 0; int mid = (l + r) >> 1; if (lower <= l && r <= upper) { return j - i; } else { T left = range_freq(bv[x].rank0(i), bv[x].rank0(j), lower, upper, l, mid, x + 1); T right = range_freq(pos[x] + bv[x].rank1(i), pos[x] + bv[x].rank1(j), lower, upper, mid, r, x + 1); return left + right; } } int range_freq(const int l, const int r, const T lower, const T upper) { return range_freq(l, r, lower, upper, 0, 1LL << height, 0); } // the minmum value between [lower, upper) in [l, r) T range_min(const int i, const int j, const T lower, const T upper, const int l, const int r, const int x, const T val) { if (i == j || r <= lower || upper <= l) return -1; if (r - l == 1) return val; int mid = (l + r) >> 1; T res = range_min(bv[x].rank0(i), bv[x].rank0(j), lower, upper, l, mid, x + 1, val); if (res < 0) { return range_min(pos[x] + bv[x].rank1(i), pos[x] + bv[x].rank1(j), lower, upper, mid, r, x + 1, val + (1LL << (height - x - 1))); } else return res; } T range_min(int l, int r, T lower, T upper) { return range_min(l, r, lower, upper, 0, 1LL << height, 0, 0); } // the max value (< val) in [l, r) T prev_value(int l, int r, T val) { int num = range_freq(l, r, 0, val); if (num == 0) return T(-1); else return k_th_smallest(num - 1, l, r); } // the min value (>= val) in [l, r) T next_value(int l, int r, T val) { int num = range_freq(l, r, 0, val); if (num == r - l) return T(-1); else return k_th_smallest(num, l, r); } }; // 2D range count template<class T> struct OrthogonalRangeCount { // inner data using ptt = pair<T, T>; const int sz; vector<T> X, Y; WaveletMatrix<T> wm; // constructor OrthogonalRangeCount(vector<ptt> candidate) : sz((int)candidate.size()), X(sz), Y(sz) { sort(candidate.begin(), candidate.end()); vector<int> vec(sz); for (int i = 0; i < sz; ++i) { X[i] = candidate[i].first, Y[i] = candidate[i].second; } sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end()); for (int i = 0; i < sz; ++i) { vec[i] = lower_bound(Y.begin(), Y.end(), candidate[i].second) - Y.begin(); } wm.init(vec, Y.size()); } // the number of points in [lx, rx) × [ly, ry) int query(const T lx, const T ly, const T rx, const T ry){ const int lxid = lower_bound(X.begin(), X.end(), lx) - X.begin(); const int rxid = lower_bound(X.begin(), X.end(), rx) - X.begin(); const int lyid = lower_bound(Y.begin(), Y.end(), ly) - Y.begin(); const int ryid = lower_bound(Y.begin(), Y.end(), ry) - Y.begin(); if (lxid >= rxid || lyid >= ryid) return 0; return wm.range_freq(lxid, rxid, lyid, ryid); } }; void AOJ_1549() { int N, Q; cin >> N; const int GETA = 1100000; vector<int> a(N); for (int i = 0; i < N; ++i) { cin >> a[i]; a[i] += GETA; } WaveletMatrix<int> wm(a); cin >> Q; while (Q--) { int l, r, d; cin >> l >> r >> d; ++r; d += GETA; int nex = wm.next_value(l, r, d); int pre = wm.prev_value(l, r, d); int res = GETA*2; if (nex != -1) res = min(res, nex - d); if (pre != -1) res = min(res, d - pre); cout << res << endl; } } int main() { AOJ_1549(); }
