peltorator

RMQ O(n + q) Farach-Colton and Bender FAST

Apr 14th, 2021 (edited)
376
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 FCBRMQ {
  6.  
  7.     namespace FCBLCA {
  8.  
  9.         namespace RMQPM1 {
  10.             const int N = 20000004;
  11.             const int K = 12; // log2(N) / 2
  12.             const int BLOCKS = 1666667; // N / K
  13.             const int LG = 21; // log2(BLOCKS)
  14.             const pair<int, int> INF = {2e9 + 7, 0};
  15.  
  16.             pair<int, int> arr[N];
  17.             pair<int, int> sparse[LG][BLOCKS];
  18.             int precalc[1 << (K - 1)][K][K + 1];
  19.             int blockType[BLOCKS];
  20.  
  21.             void buildSparse(int n) {
  22.                 for (int block = 0; block < BLOCKS; block++) {
  23.                     int l = block * K;
  24.                     int r = min(l + K, n);
  25.                     pair<int, int> blockMin = arr[l];
  26.                     for (int i = l + 1; i < r; i++) {
  27.                         blockMin = min(blockMin, arr[i]);
  28.                         if (arr[i].first == arr[i - 1].first + 1) {
  29.                             blockType[block] |= (1 << (i - l - 1));
  30.                         }
  31.                     }
  32.                     sparse[0][block] = blockMin;
  33.                 }
  34.  
  35.                 for (int bit = 1; bit < LG; bit++) {
  36.                     for (int i = 0; i + (1 << bit) <= BLOCKS; i++) {
  37.                         sparse[bit][i] = min(sparse[bit - 1][i], sparse[bit - 1][i + (1 << (bit - 1))]);
  38.                     }
  39.                 }
  40.             }
  41.  
  42.             void buildPrecalc() {
  43.                 for (int mask = 0; mask < (1 << (K - 1)); mask++) {
  44.                     for (int l = 0; l < K; l++) {
  45.                         precalc[mask][l][l] = -1;
  46.                         int curmin = numeric_limits<int>::max();
  47.                         int curval = 0;
  48.                         for (int r = l; r < K; r++) {
  49.                             if (curval < curmin) {
  50.                                 precalc[mask][l][r + 1] = r;
  51.                                 curmin = curval;
  52.                             } else {
  53.                                 precalc[mask][l][r + 1] = precalc[mask][l][r];
  54.                             }
  55.                             if ((mask >> r) & 1) {
  56.                                 curval++;
  57.                             } else {
  58.                                 curval--;
  59.                             }
  60.                         }
  61.                     }
  62.                 }
  63.             }
  64.  
  65.             void init(int n) {
  66.                 buildSparse(n);
  67.                 buildPrecalc();
  68.             }
  69.          
  70.             pair<int, int> findShort(int left, int right) { // left and right are in one block
  71.                 if (left == right) {
  72.                     return INF;
  73.                 }
  74.                 int block = left / K;
  75.                 pair<int, int> ans = arr[block * K + precalc[blockType[block]][left - block * K][right - block * K]];
  76.                 return ans;
  77.             }
  78.  
  79.             pair<int, int> findLong(int lblock, int rblock) {
  80.                 if (lblock == rblock) {
  81.                     return INF;
  82.                 }
  83.                 int bit = 31 - __builtin_clz(rblock - lblock);
  84.                 pair<int, int> ans = min(sparse[bit][lblock], sparse[bit][rblock - (1 << bit)]);
  85.                 return ans;
  86.             }
  87.  
  88.             pair<int, int> findMin(int left, int right) { // [left; right)
  89.                 int lblock = left / K;
  90.                 int rblock = right / K;
  91.                 if (lblock == rblock) {
  92.                     return findShort(left, right);
  93.                 } else {
  94.                     return min(findLong(lblock + 1, rblock), min(findShort(left, (lblock + 1) * K), findShort(rblock * K, right)));
  95.                 }
  96.             }
  97.         }
  98.  
  99.         const int N = 10000000;
  100.  
  101.         int left[N];
  102.         int right[N];
  103.         int timein[N];
  104.         pair<int, int> recStack[N];
  105.  
  106.         int dfs(int root) {
  107.             int stackSize = 1;
  108.             recStack[0] = {0, root};
  109.             timein[0] = 0;
  110.             int eulerSize = 0;
  111.             int lastVertex = root;
  112.             while (stackSize > 0) {
  113.                 int curVertex = recStack[stackSize - 1].second;
  114.                 int depth = recStack[stackSize - 1].first;
  115.                 RMQPM1::arr[eulerSize++] = recStack[stackSize - 1];
  116.                 if (right[curVertex] != lastVertex) {
  117.                      if (left[curVertex] != lastVertex && left[curVertex] != -1) {
  118.                         timein[left[curVertex]] = eulerSize;
  119.                         recStack[stackSize++] = {depth + 1, left[curVertex]};
  120.                     } else if (right[curVertex] != -1) {
  121.                         timein[right[curVertex]] = eulerSize;
  122.                         recStack[stackSize++] = {depth + 1, right[curVertex]};
  123.                     } else {
  124.                         stackSize--;
  125.                     }
  126.                 } else {
  127.                     stackSize--;
  128.                 }
  129.                 lastVertex = curVertex;
  130.             }
  131.             return eulerSize;
  132.         }
  133.  
  134.         void init(int root) {
  135.             int eulerSize = dfs(root);
  136.             RMQPM1::init(eulerSize);
  137.         }
  138.  
  139.         int findLCA(int u, int v) {
  140.             if (timein[u] > timein[v]) {
  141.                 swap(u, v);
  142.             }
  143.             return RMQPM1::findMin(timein[u], timein[v] + 1).second;
  144.         }
  145.     }
  146.  
  147.     const int N = 10000000;
  148.     int arr[N];
  149.     int rightBranch[N];
  150.  
  151.     int buildTreap(int n) {
  152.         FCBLCA::left[0] = FCBLCA::right[0] = -1;
  153.         int branchSize = 0;
  154.         rightBranch[branchSize++] = 0;
  155.         for (int i = 1; i < n; i++) {
  156.             FCBLCA::left[i] = FCBLCA::right[i] = -1;
  157.             int lastVertex = -1;
  158.             while (branchSize > 0 && arr[rightBranch[branchSize - 1]] >= arr[i]) {
  159.                 lastVertex = rightBranch[--branchSize];
  160.             }
  161.             FCBLCA::left[i] = lastVertex;
  162.             if (branchSize > 0) {
  163.                 FCBLCA::right[rightBranch[branchSize - 1]] = i;
  164.             }
  165.             rightBranch[branchSize++] = i;
  166.         }
  167.         return rightBranch[0];
  168.     }
  169.  
  170.     void init(int n) {
  171.         int root = buildTreap(n);
  172.         FCBLCA::init(root);
  173.     }
  174.  
  175.     int findMin(int l, int r) {
  176.         return arr[FCBLCA::findLCA(l, r - 1)];
  177.     }
  178. };
  179.  
  180. // ~~ 18 * n memory
  181. // can me optimized to ~~ 12 * n if we reuse arrays
  182.  
  183. int main() {
  184.     int n;
  185.     cin >> n;
  186.     for (int i = 0; i < n; i++) {
  187.         cin >> FCBRMQ::arr[i];
  188.     }
  189.     FCBRMQ::init(n);
  190.     int q;
  191.     cin >> q;
  192.     for (int i = 0; i < q; i++) {
  193.         int left, right;
  194.         cin >> left >> right;
  195.         left--; // 0-indexing and half-intervals
  196.         cout << FCBRMQ::findMin(left, right) << '\n';
  197.     }
  198.     return 0;
  199. }
  200.  
RAW Paste Data