Advertisement
peltorator

RMQ O(n + q) Bit Magic FAST

Apr 14th, 2021
840
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. namespace BitRMQ {
  6.     static const int K = 32;
  7.     static const int N = 20000064;
  8.     static const int BLOCKS = 625002;
  9.     static const int LOG = 21;
  10.     static const int INF = 1e9 + 7;
  11.  
  12.     int arr[N];
  13.     int sparse[LOG][BLOCKS];
  14.     int precalc[N];
  15.     int n;
  16.  
  17.     void buildSparse() {
  18.         for (int block = 0; block < BLOCKS; block++) {
  19.             int l = block * K;
  20.             int r = min(l + K, n);
  21.             int blockMin = arr[l];
  22.             for (int i = l + 1; i < r; i++) {
  23.                 blockMin = min(blockMin, arr[i]);
  24.             }
  25.             sparse[0][block] = blockMin;
  26.         }
  27.  
  28.         for (int bit = 1; bit < LOG; bit++) {
  29.             for (int i = 0; i + (1 << bit) <= BLOCKS; i++) {
  30.                 sparse[bit][i] = min(sparse[bit - 1][i], sparse[bit - 1][i + (1 << (bit - 1))]);
  31.             }
  32.         }
  33.     }
  34.  
  35.     void buildPrecalc() {
  36.         int ms = 0;
  37.         for (int i = 0; i < n; i++) {
  38.             precalc[i] = ms;
  39.             ms <<= 1;
  40.             while (ms != 0) {
  41.                 int bt = __builtin_ctz(ms);
  42.                 if (arr[i - bt] < arr[i]) {
  43.                     break;
  44.                 }
  45.                 ms ^= (1 << bt);
  46.             }
  47.             ms |= 1;
  48.         }
  49.         precalc[n] = ms;
  50.     }
  51.  
  52.     void init(int arrayLen) {
  53.         n = arrayLen;
  54.         buildSparse();
  55.         buildPrecalc();
  56.     }
  57.  
  58.    
  59.     int findShort(int left, int right) { // left and right are in one block
  60.         if (left >= right) {
  61.             return INF;
  62.         }
  63.         int len = right - left;
  64.         int maxBit = 32 - __builtin_clz(precalc[right] & ((1LL << len) - 1));
  65.         int ans = arr[right - maxBit];
  66.         return ans;
  67.     }
  68.  
  69.     int findLong(int lblock, int rblock) {
  70.         if (lblock == rblock) {
  71.             return INF;
  72.         }
  73.         int bit = 31 - __builtin_clz(rblock - lblock);
  74.         int ans = min(sparse[bit][lblock], sparse[bit][rblock - (1 << bit)]);
  75.         return ans;
  76.     }
  77.  
  78.     int findMin(int left, int right) { // [left; right)
  79.         int lblock = left / K;
  80.         int rblock = right / K;
  81.         if (lblock == rblock) {
  82.             return findShort(left, right);
  83.         } else {
  84.             return min(findLong(lblock + 1, rblock), min(findShort(left, (lblock + 1) * K), findShort(rblock * K, right)));
  85.         }
  86.     }
  87. }
  88.  
  89. int main() {
  90.     int n;
  91.     cin >> n;
  92.     for (int i = 0; i < n; i++) {
  93.         cin >> BitRMQ::arr[i];
  94.     }
  95.     BitRMQ::init(n);
  96.     int q;
  97.     cin >> q;
  98.     for (int i = 0; i < q; i++) {
  99.         int left, right;
  100.         cin >> left >> right;
  101.         left--; // 0-indexing and half-intervals
  102.         cout << BitRMQ::findMin(left, right) << '\n';
  103.     }
  104.     return 0;
  105. }
  106.  
Advertisement
RAW Paste Data Copied
Advertisement