結果
問題 | No.1332 Range Nearest Query |
ユーザー | outline |
提出日時 | 2021-01-08 22:26:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 596 ms / 2,500 ms |
コード長 | 6,931 bytes |
コンパイル時間 | 2,266 ms |
コンパイル使用メモリ | 143,856 KB |
最終ジャッジ日時 | 2025-01-17 12:43:18 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>#include <unordered_set>using namespace std;using ll = long long;using P = pair<int, int>;constexpr int INF = 1001001001;constexpr int mod = 1000000007;// constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}struct SuccinctIndexableDictionary {size_t length, blocks;vector<unsigned> bit, sum;SuccinctIndexableDictionary() = default;SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {bit.assign(blocks, 0U);sum.assign(blocks, 0U);}void set(int k){bit[k >> 5] |= 1U << (k & 31);}void build(){sum[0] = 0U;for(int i = 1; i < blocks; ++i){sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);}}bool operator[](int k){return (bool((bit[k >> 5] >> (k & 31)) & 1));}int rank(int k){return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));}// f : bit flagint rank(bool f, int k){return (f ? rank(k) : k - rank(k));}};template<typename T, int MAXLOG>struct WaveletMatrix {size_t length;SuccinctIndexableDictionary matrix[MAXLOG];int mid[MAXLOG];WaveletMatrix() = default;WaveletMatrix(vector<T> v) : length(v.size()) {vector<T> zero(length), one(length);for(int level = MAXLOG - 1; level >= 0; --level){matrix[level] = SuccinctIndexableDictionary(length + 1);int left = 0, right = 0;for(int i = 0; i < length; ++i){if(((v[i] >> level) & 1)){matrix[level].set(i);one[right++] = v[i];}else{zero[left++] = v[i];}}mid[level] = left;matrix[level].build();v.swap(zero);for(int i = 0; i < right; ++i){v[left + i] = one[i];}}}pair<int, int> succ(bool f, int l, int r, int level){return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};}T access(int k){T ret = 0;for(int level = MAXLOG - 1; level >= 0; --level){bool f = matrix[level][k];if(f) ret |= T(1) << level;k = matrix[level].rank(f, k) + mid[level] * f;}return ret;}T operator[](const int& k){return access(k);}int rank(const T& x, int r){int l = 0;for(int level = MAXLOG - 1; level >= 0; --level){tie(l, r) = succ((x >> level) & 1, l, r, level);}return r - l;}T kth_smallest(int l, int r, int k){assert(0 <= k && k < r - l);T ret = 0;for(int level = MAXLOG - 1; level >= 0; --level){int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);bool f = cnt <= k;if(f){ret |= T(1) << level;k -= cnt;}tie(l, r) = succ(f, l, r, level);}return ret;}T kth_largest(int l, int r, int k){return kth_smallest(l, r, r - l - k - 1);}int range_freq(int l, int r, T upper){int ret = 0;for(int level = MAXLOG - 1; level >= 0; --level){bool f = ((upper >> level) & 1);if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);tie(l, r) = succ(f, l, r, level);}return ret;}int range_freq(int l, int r, T lower, T upper){return range_freq(l, r, upper) - range_freq(l, r, lower);}T prev_value(int l, int r, T upper){int cnt = range_freq(l, r, upper);return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);}T next_value(int l, int r, T lower){int cnt = range_freq(l, r, lower);return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);}};template<typename T, int MAXLOG>struct CompressedWaveletMatrix {WaveletMatrix<int, MAXLOG> mat;vector<T> ys;CompressedWaveletMatrix(const vector<T>& v) : ys(v) {sort(begin(ys), end(ys));ys.erase(unique(ys.begin(), ys.end()), ys.end());vector<int> t(v.size());for(int i = 0; i < (int)v.size(); ++i) t[i] = get(v[i]);mat = WaveletMatrix<int, MAXLOG>(t);}inline int get(const T& x){return lower_bound(begin(ys), end(ys), x) - begin(ys);}T access(int k){return ys[mat.access(k)];}T operator[](const int& k){return access(k);}int rank(const T& x, int r){auto pos = get(x);if(pos == ys.size() || ys[pos] != x) return 0;return mat.rank(pos, r);}T kth_smallest(int l, int r, int k){return ys[mat.kth_smallest(l, r, k)];}T kth_largest(int l, int r, int k){return ys[mat.kth_largest(l, r, k)];}int range_freq(int l, int r, T upper){return mat.range_freq(l, r, get(upper));}int range_freq(int l, int r, T lower, T upper){return mat.range_freq(l, r, get(lower), get(upper));}T prev_value(int l, int r, T upper){auto ret = mat.prev_value(l, r, get(upper));return ret == -1 ? T(-1) : ys[ret];}T next_value(int l, int r, T lower){auto ret = mat.next_value(l, r, get(lower));return ret == -1 ? T(-1) : ys[ret];}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N, Q, l, r, x;cin >> N;vector<int> X(N);for(int i = 0; i < N; ++i) cin >> X[i];CompressedWaveletMatrix<int, 25> cwm(X);cin >> Q;for(int q = 0; q < Q; ++q){cin >> l >> r >> x;--l;if(cwm.range_freq(l, r, x, x + 1)){cout << 0 << '\n';}else{int prv = cwm.prev_value(l, r, x);int nxt = cwm.next_value(l, r, x);int ans = INF;if(prv != -1) chmin(ans, x - prv);if(nxt != -1) chmin(ans, nxt - x);cout << ans << '\n';}}return 0;}