peltorator

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

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