peltorator

RMQ+-1 O(n + q) FAST

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