This documentation is automatically generated by online-judge-tools/verification-helper
#include "other/offline-rmq.hpp"
#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;
}