_Solenya_'s blog

By _Solenya_, 3 years ago, In English

HI I just found another solution for RMQ problem similar to Arpa's trick the idea is the same (using DSU for offline queries) and even the order of algorithms are the same but its easier to implement and probably easier to understand.

Problem : Given array a of n integers, and q queries, for each query print the maximum value in range [L, R].

Solution :

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 10;
int n, q, a[MAXN], par[MAXN], ans[MAXN], l[MAXN];
vector<int> R[MAXN];

int getpar(int v) {
	if (par[v] == v)
		return v;
	int t = par[v];
	par[v] = getpar(par[v]);
	a[v] = min(a[v], a[t]);
	return par[v];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i], par[i] = i;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int r;
		cin >> l[i] >> r;
        //finding answer to queries which range ends in i
	for (int i = 0; i < n; i++) {
		if (i >= 1)
			par[i - 1] = i;
		for (int j = 0; j < R[i].size(); j++)
			getpar(l[R[i][j]]), ans[R[i][j]] = a[l[R[i][j]]];
	for (int i = 0; i < q; i++)
		cout << ans[i] << '\n';

some comment on code : consider tree of DSU. In each step, the path from vertex number v to the root of its component contains the minimum value in the range [l, the last R that we're finding answer to] (among a[v], a[par[v]], ..... a[root of component]) to find the minimum, we use path-compression technique using DSU then we extend the range of R that we're finding answer to.

Read more »

  • Vote: I like it
  • +20
  • Vote: I do not like it