OfflineRMQ.cpp

• View this file on GitHub
• Last update: 2023-02-27 10:03:35-03:00

Depends on

• DSU.cpp
• bits/stdc++.h

Code

#ifndef _LIB_OFFLINE_RMQ
#define _LIB_OFFLINE_RMQ
#include <bits/stdc++.h>
#include "DSU.cpp"

namespace lib {
using namespace std;

// O(n + qlogn)
template<typename T, typename U = T>
vector<T> offline_rmq(const vector<T>& v, const vector<pair<U, U>>& qrs) {
  int n = v.size();
  vector<vector<pair<U, int>>> cont(n);
  for(int i = 0; i < (int)qrs.size(); i++) {
    auto p = qrs[i];
    cont[p.second].push_back({p.first, i});
  }
  vector<T> ans(qrs.size());

  CompressedDSU dsu(n);
  vector<U> s;
  for(int i = 0; i < n; i++) {
    while(!s.empty() && v[s.back()] > v[i]) {
      dsu.parent(s.back()) = i;
      s.pop_back();
    }
    s.push_back(i);
    for(auto p : cont[i]) {
      ans[p.second] = v[dsu[p.first]];
    }
  }
  return ans;
}
} // namespace lib

#endif

#line 1 "OfflineRMQ.cpp"


#include <bits/stdc++.h>
#line 1 "DSU.cpp"


#line 4 "DSU.cpp"

namespace lib {
using namespace std;

struct DSU {
  vector<int> p, ptime, sz;
  int tempo = 0;
  int merges = 0;
  pair<int, int> last_merge_ = {-1, -1};

  DSU(int n = 0) : p(n), ptime(n, 1e9), sz(n, 1) { iota(p.begin(), p.end(), 0); }

  int make_node() {
    int i = p.size();
    p.emplace_back(i);
    ptime.emplace_back(0);
    sz.emplace_back(1);
    return 1;
  }

  int get(int i, int at) const {
    return p[i] == i ? i : (at >= ptime[i] ? get(p[i], at) : i);
  }

  int operator[](int i) const { return get(i, tempo); }

  int merge(int u, int v) {
    u = (*this)[u], v = (*this)[v];
    if (u == v)
      return 0;
    if (sz[u] < sz[v])
      swap(u, v);
    p[v] = u;
    ptime[v] = ++tempo;
    sz[u] += sz[v];
    last_merge_ = {v, u};
    merges++;
    return 1;
  }
  pair<int, int> last_merge() const {
    return last_merge_;
  }

  int n_comps() const { return (int)p.size() - merges; }
};

struct CompressedDSU {
  vector<int> p;
  CompressedDSU(int n = 0) : p(n) { iota(p.begin(), p.end(), 0); }
  int get(int i) {
    return p[i] == i ? i : p[i] = get(p[i]);
  }
  int operator[](int i) { return get(i); }
  int& parent(int i) { return p[i]; }
};

struct FastDSU {
  vector<int> p, sz;
  int merges = 0;
  pair<int, int> last_merge_ = {-1, -1};
  FastDSU(int n = 0) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }

  int get(int i) {
    return p[i] == i ? i : p[i] = get(p[i]);
  }
  int operator[](int i) { return get(i); }

  int merge(int u, int v) {
    u = get(u), v = get(v);
    if(u == v) return 0;
    if(sz[u] < sz[v])
      swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    merges++;
    last_merge_ = {v, u};
    return 1;
  }
  pair<int, int> last_merge() const {
    return last_merge_;
  }
  int n_comps() const { return (int)p.size() - merges; }
};
} // namespace lib


#line 5 "OfflineRMQ.cpp"

namespace lib {
using namespace std;

// O(n + qlogn)
template<typename T, typename U = T>
vector<T> offline_rmq(const vector<T>& v, const vector<pair<U, U>>& qrs) {
  int n = v.size();
  vector<vector<pair<U, int>>> cont(n);
  for(int i = 0; i < (int)qrs.size(); i++) {
    auto p = qrs[i];
    cont[p.second].push_back({p.first, i});
  }
  vector<T> ans(qrs.size());

  CompressedDSU dsu(n);
  vector<U> s;
  for(int i = 0; i < n; i++) {
    while(!s.empty() && v[s.back()] > v[i]) {
      dsu.parent(s.back()) = i;
      s.pop_back();
    }
    s.push_back(i);
    for(auto p : cont[i]) {
      ans[p.second] = v[dsu[p.first]];
    }
  }
  return ans;
}
} // namespace lib

Back to top page