peltorator

RMQ+-1 O(n + q)

Apr 5th, 2021 (edited)
585
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 RMQPM1 {
  6.     vector<int> arr;
  7.     vector<vector<int>> sparse;
  8.     vector<vector<vector<int>>> precalc;
  9.     vector<int> blockType;
  10.     vector<int> logs;
  11.     int n;
  12.     int k;
  13.     int blocks;
  14.     int lg;
  15.     const int INF = 1e9 + 7;
  16.  
  17.  
  18.     RMQPM1(const vector<int>& inputArray) {
  19.         arr = inputArray;
  20.         n = arr.size();
  21.         k = ceil(log2(n + 1) / 2);
  22.         blocks = (n + k - 1) / k;
  23.         lg = ceil(log2(blocks + 1));
  24.         sparse.assign(lg, vector<int>(blocks, 0));
  25.         precalc.assign((1 << (k - 1)), vector<vector<int>>(k, vector<int>(k + 1, 0)));
  26.         blockType.assign(blocks, 0);
  27.         logs.assign(blocks, 0);
  28.        
  29.         buildLogs();
  30.         buildSparse();
  31.         buildPrecalc();
  32.     }
  33.  
  34.     void buildLogs() {
  35.         logs[1] = 0;
  36.         for (int i = 2; i < blocks; i++) {
  37.             logs[i] = logs[i >> 1] + 1;
  38.         }
  39.     }
  40.  
  41.     void buildSparse() {
  42.         for (int block = 0; block < blocks; block++) {
  43.             int l = block * k;
  44.             int r = min(l + k, n);
  45.             int blockMin = arr[l];
  46.             for (int i = l + 1; i < r; i++) {
  47.                 blockMin = min(blockMin, arr[i]);
  48.                 if (arr[i] == arr[i - 1] + 1) {
  49.                     blockType[block] |= (1 << (i - l - 1));
  50.                 }
  51.             }
  52.             sparse[0][block] = blockMin;
  53.         }
  54.  
  55.         for (int bit = 1; bit < lg; bit++) {
  56.             for (int i = 0; i + (1 << bit) <= blocks; i++) {
  57.                 sparse[bit][i] = min(sparse[bit - 1][i], sparse[bit - 1][i + (1 << (bit - 1))]);
  58.             }
  59.         }
  60.     }
  61.  
  62.     void buildPrecalc() {
  63.         for (int mask = 0; mask < (1 << (k - 1)); mask++) {
  64.             for (int l = 0; l < k; l++) {
  65.                 precalc[mask][l][l] = INF;
  66.                 int curval = 0;
  67.                 for (int r = l; r < k; r++) {
  68.                     precalc[mask][l][r + 1] = min(precalc[mask][l][r], curval);
  69.                     if ((mask >> r) & 1) {
  70.                         curval++;
  71.                     } else {
  72.                         curval--;
  73.                     }
  74.                 }
  75.             }
  76.         }
  77.     }
  78.    
  79.     int findShort(int left, int right) { // left and right are in one block
  80.         int block = left / k;
  81.         int ans = precalc[blockType[block]][left - block * k][right - block * k] + arr[left];
  82.         return ans;
  83.     }
  84.  
  85.     int findLong(int lblock, int rblock) {
  86.         if (lblock == rblock) {
  87.             return INF;
  88.         }
  89.         int bit = logs[rblock - lblock];
  90.         int ans = min(sparse[bit][lblock], sparse[bit][rblock - (1 << bit)]);
  91.         return ans;
  92.     }
  93.  
  94.     int findMin(int left, int right) { // [left; right)
  95.         int lblock = left / k;
  96.         int rblock = right / k;
  97.         if (lblock == rblock) {
  98.             return findShort(left, right);
  99.         } else {
  100.             return min(findLong(lblock + 1, rblock), min(findShort(left, (lblock + 1) * k), findShort(rblock * k, right)));
  101.         }
  102.     }
  103. };
  104.  
  105. int main() {
  106.     int n;
  107.     cin >> n;
  108.     vector<int> arr(n);
  109.     for (int& elem : arr) {
  110.         cin >> elem;
  111.     }
  112.     RMQPM1 rmq(arr);
  113.     int q;
  114.     cin >> q;
  115.     for (int i = 0; i < q; i++) {
  116.         int left, right;
  117.         cin >> left >> right;
  118.         left--; // 0-indexing and half-intervals
  119.         cout << rmq.findMin(left, right) << '\n';
  120.     }
  121.     return 0;
  122. }
  123.  
RAW Paste Data