peltorator

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

Apr 7th, 2021 (edited)
390
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 = 1e6, M = N;
  6.  
  7. int arr[N];
  8. int ans[N];
  9. int minimaStack[N];
  10.  
  11. int ancestor[N];
  12. int setSize[N];
  13. int setMinimum[N];
  14.  
  15. int l[M], r[M];
  16. int sortedQueriesIds[M];
  17. int indexCounts[N + 1];
  18.  
  19. void initDSU(int n) {
  20.     for (int i = 0; i < n; i++) {
  21.         ancestor[i] = i;
  22.         setSize[i] = 1;
  23.         setMinimum[i] = arr[i];
  24.     }
  25. }
  26.  
  27. int findRoot(int v) {
  28.     if (ancestor[v] == v) {
  29.         return v;
  30.     } else {
  31.         return ancestor[v] = findRoot(ancestor[v]);
  32.     }
  33. }
  34.  
  35. void unionSets(int u, int v) {
  36.     u = findRoot(u);
  37.     v = findRoot(v);
  38.     if (setSize[u] < setSize[v]) {
  39.         swap(u, v);
  40.     }
  41.     setSize[u] += setSize[v];
  42.     ancestor[v] = u;
  43.     setMinimum[u] = min(setMinimum[u], setMinimum[v]);
  44. }
  45.  
  46. int findSetMinimum(int v) {
  47.     return setMinimum[findRoot(v)];
  48. }
  49.  
  50. void solveRMQ(int n, int q) {
  51.     for (int i = 0; i < q; i++) {
  52.         indexCounts[r[i] + 1]++;
  53.     }
  54.     for (int i = 0; i < N; i++) {
  55.         indexCounts[i + 1] += indexCounts[i];
  56.     }
  57.     for (int i = 0; i < q; i++) {
  58.         sortedQueriesIds[indexCounts[r[i]]++] = i;
  59.     }
  60.     initDSU(n);
  61.     int stackSize = 0;
  62.     int sortedQueriesIter = 0;
  63.     for (int i = 0; i < n; i++) {
  64.         while (stackSize > 0 && arr[i] <= arr[minimaStack[stackSize - 1]]) {
  65.             unionSets(i, minimaStack[stackSize - 1]);
  66.             stackSize--;
  67.         }
  68.         minimaStack[stackSize++] = i;
  69.         while (sortedQueriesIter < q && r[sortedQueriesIds[sortedQueriesIter]] == i) {
  70.             int curid = sortedQueriesIds[sortedQueriesIter++];
  71.             ans[curid] = findSetMinimum(l[curid]);
  72.         }
  73.     }
  74. }
  75.  
  76. int main() {
  77.     ios::sync_with_stdio(0);
  78.     cin.tie(0);
  79.  
  80.     int n;
  81.     cin >> n;
  82.     for (int i = 0; i < n; i++) {
  83.         cin >> arr[i];
  84.     }
  85.     int q;
  86.     cin >> q;
  87.     for (int i = 0; i < q; i++) {
  88.         cin >> l[i] >> r[i];
  89.         l[i]--;
  90.         r[i]--; // 0-indexing
  91.     }
  92.     solveRMQ(n, q);
  93.     for (int i = 0; i < q; i++) {
  94.         cout << ans[i] << '\n';
  95.     }
  96.     return 0;
  97. }
  98.  
RAW Paste Data