peltorator

RMQ O(n + q) Bit Magic FAST

Apr 14th, 2021
479
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.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×