peltorator

RMQ offline O((n + q) * alpha) Tarjan

Apr 5th, 2021 (edited)
558
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 DSU {
  6.     vector<int> ancestor;
  7.     vector<int> setSize;
  8.     vector<int> setMinimum;
  9.  
  10.     DSU(const vector<int>& arr) {
  11.         ancestor.assign(arr.size(), 0);
  12.         setSize.assign(arr.size(), 1);
  13.         setMinimum = arr;
  14.         for (size_t i = 0; i < arr.size(); i++) {
  15.             ancestor[i] = i;
  16.         }
  17.     }
  18.  
  19.     int findRoot(int v) {
  20.         if (ancestor[v] == v) {
  21.             return v;
  22.         } else {
  23.             return ancestor[v] = findRoot(ancestor[v]);
  24.         }
  25.     }
  26.  
  27.     void unionSets(int u, int v) {
  28.         u = findRoot(u);
  29.         v = findRoot(v);
  30.         if (setSize[u] < setSize[v]) {
  31.             swap(u, v);
  32.         }
  33.         setSize[u] += setSize[v];
  34.         ancestor[v] = u;
  35.         setMinimum[u] = min(setMinimum[u], setMinimum[v]);
  36.     }
  37.  
  38.     int findSetMinimum(int v) {
  39.         return setMinimum[findRoot(v)];
  40.     }
  41. };
  42.  
  43. vector<int> solveRMQ(const vector<int>& arr, const vector<pair<int, int>>& queries) {
  44.     int n = arr.size();
  45.     int q = queries.size();
  46.     vector<vector<pair<int, int>>> queriesForRightBounds(n);
  47.     for (int i = 0; i < q; i++) {
  48.         int left = queries[i].first, right = queries[i].second;
  49.         queriesForRightBounds[right].emplace_back(left, i);
  50.     }
  51.     DSU dsu(arr);
  52.     stack<int> minimaStack;
  53.     vector<int> ans(q);
  54.     for (int i = 0; i < n; i++) {
  55.         while (!minimaStack.empty() && arr[i] <= arr[minimaStack.top()]) {
  56.             dsu.unionSets(i, minimaStack.top());
  57.             minimaStack.pop();
  58.         }
  59.         minimaStack.push(i);
  60.         for (auto [left, qind] : queriesForRightBounds[i]) {
  61.             ans[qind] = dsu.findSetMinimum(left);
  62.         }
  63.     }
  64.     return ans;
  65. }
  66.  
  67. int main() {
  68.     int n;
  69.     cin >> n;
  70.     vector<int> arr(n);
  71.     for (int& elem : arr) {
  72.         cin >> elem;
  73.     }
  74.     int q;
  75.     cin >> q;
  76.     vector<pair<int, int>> queries(q);
  77.     for (auto& [left, right] : queries) {
  78.         cin >> left >> right;
  79.         left--;
  80.         right--; // 0-indexing
  81.     }
  82.     vector<int> ans = solveRMQ(arr, queries);
  83.     for (int val : ans) {
  84.         cout << val << '\n';
  85.     }
  86.     return 0;
  87. }
  88.  
RAW Paste Data