peltorator

RMQ O(n + q) Bit Magic

Apr 7th, 2021 (edited)
159
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct BitRMQ {
  6.     vector<int> arr;
  7.     vector<vector<int>> sparse;
  8.     vector<int> precalc;
  9.     int n;
  10.     int k;
  11.     int blocks;
  12.     int lg;
  13.     const int INF = 1e9 + 7;
  14.  
  15.     BitRMQ(const vector<int>& inputArray) {
  16.         arr = inputArray;
  17.         n = arr.size();
  18.         k = 32;
  19.         blocks = (n + k - 1) / k;
  20.         lg = ceil(log2(blocks + 1));
  21.         sparse.assign(lg, vector<int>(blocks, 0));
  22.         precalc.assign(n + 1, 0);
  23.         buildSparse();
  24.         buildPrecalc();
  25.     }
  26.  
  27.     void buildSparse() {
  28.         for (int block = 0; block < blocks; block++) {
  29.             int l = block * k;
  30.             int r = min(l + k, n);
  31.             int blockMin = arr[l];
  32.             for (int i = l + 1; i < r; i++) {
  33.                 blockMin = min(blockMin, arr[i]);
  34.             }
  35.             sparse[0][block] = blockMin;
  36.         }
  37.  
  38.         for (int bit = 1; bit < lg; bit++) {
  39.             for (int i = 0; i + (1 << bit) <= blocks; i++) {
  40.                 sparse[bit][i] = min(sparse[bit - 1][i], sparse[bit - 1][i + (1 << (bit - 1))]);
  41.             }
  42.         }
  43.     }
  44.  
  45.     void buildPrecalc() {
  46.         int ms = 0;
  47.         stack<int> minimaStack;
  48.         for (int i = 0; i < n; i++) {
  49.             precalc[i] = ms;
  50.             ms <<= 1;
  51.             ms |= 1;
  52.             while (!minimaStack.empty() && arr[minimaStack.top()] > arr[i]) {
  53.                 int len = i - minimaStack.top();
  54.                 if (len < 32) {
  55.                     ms ^= (1 << len);
  56.                 }
  57.                 minimaStack.pop();
  58.             }
  59.             minimaStack.push(i);
  60.         }
  61.         precalc[n] = ms;
  62.     }
  63.    
  64.     int findShort(int left, int right) { // left and right are in one block
  65.         if (left >= right) {
  66.             return INF;
  67.         }
  68.         int len = right - left;
  69.         int maxBit = 32 - __builtin_clz(precalc[right] & ((1LL << len) - 1));
  70.         int ans = arr[right - maxBit];
  71.         return ans;
  72.     }
  73.  
  74.     int findLong(int lblock, int rblock) {
  75.         if (lblock == rblock) {
  76.             return INF;
  77.         }
  78.         int bit = 31 - __builtin_clz(rblock - lblock);
  79.         int ans = min(sparse[bit][lblock], sparse[bit][rblock - (1 << bit)]);
  80.         return ans;
  81.     }
  82.  
  83.     int findMin(int left, int right) { // [left; right)
  84.         int lblock = left / k;
  85.         int rblock = right / k;
  86.         if (lblock == rblock) {
  87.             return findShort(left, right);
  88.         } else {
  89.             return min(findLong(lblock + 1, rblock), min(findShort(left, (lblock + 1) * k), findShort(rblock * k, right)));
  90.         }
  91.     }
  92. };
  93.  
  94. int main() {
  95.     int n;
  96.     cin >> n;
  97.     vector<int> arr(n);
  98.     for (int& elem : arr) {
  99.         cin >> elem;
  100.     }
  101.     BitRMQ rmq(arr);
  102.     int q;
  103.     cin >> q;
  104.     for (int i = 0; i < q; i++) {
  105.         int left, right;
  106.         cin >> left >> right;
  107.         left--; // 0-indexing and half-intervals
  108.         cout << rmq.findMin(left, right) << '\n';
  109.     }
  110.     return 0;
  111. }
  112.  
RAW Paste Data