Offline RMQ (other/offline-rmq.hpp)

• View this file on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "other/offline-rmq.hpp"

Depends on

• Union Find (structure/union-find/union-find.hpp)

Verified with

• test/verify/yosupo-staticrmq-6.test.cpp

Code

#include "../structure/union-find/union-find.hpp"

/**
 * @brief Offline RMQ
 **/
template< typename Comp >
vector< int > offline_rmq(vector< pair< int, int > > &qs, const Comp &comp) {
  int n = 0;
  for(auto&[l, r]: qs) n = max(n, r);
  UnionFind uf(n);
  vector< int > st(n), mark(n), ans(qs.size());
  int top = -1;
  for(auto&[l, r]: qs) mark[r - 1]++;
  vector< vector< int > > q(n);
  for(int i = 0; i < n; i++) {
    q[i].reserve(mark[i]);
  }
  for(int i = 0; i < qs.size(); i++) {
    q[qs[i].second - 1].emplace_back(i);
  }
  for(int i = 0; i < n; i++) {
    while(~top and not comp(st[top], i)) {
      uf.unite(st[top--], i);
    }
    st[++top] = i;
    mark[uf.find(i)] = i;
    for(auto &j: q[i]) {
      ans[j] = mark[uf.find(qs[j].first)];
    }
  }
  return ans;
}

#line 2 "structure/union-find/union-find.hpp"

struct UnionFind {
  vector< int > data;

  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return false;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if(data[k] < 0) return (k);
    return data[k] = find(data[k]);
  }

  int size(int k) {
    return -data[find(k)];
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  vector< vector< int > > groups() {
    int n = (int) data.size();
    vector< vector< int > > ret(n);
    for(int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(remove_if(begin(ret), end(ret), [&](const vector< int > &v) {
      return v.empty();
    }), end(ret));
    return ret;
  }
};
#line 2 "other/offline-rmq.hpp"

/**
 * @brief Offline RMQ
 **/
template< typename Comp >
vector< int > offline_rmq(vector< pair< int, int > > &qs, const Comp &comp) {
  int n = 0;
  for(auto&[l, r]: qs) n = max(n, r);
  UnionFind uf(n);
  vector< int > st(n), mark(n), ans(qs.size());
  int top = -1;
  for(auto&[l, r]: qs) mark[r - 1]++;
  vector< vector< int > > q(n);
  for(int i = 0; i < n; i++) {
    q[i].reserve(mark[i]);
  }
  for(int i = 0; i < qs.size(); i++) {
    q[qs[i].second - 1].emplace_back(i);
  }
  for(int i = 0; i < n; i++) {
    while(~top and not comp(st[top], i)) {
      uf.unite(st[top--], i);
    }
    st[++top] = i;
    mark[uf.find(i)] = i;
    for(auto &j: q[i]) {
      ans[j] = mark[uf.find(qs[j].first)];
    }
  }
  return ans;
}

Back to top page