Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

_Solenya_'s blog

By _Solenya_, 17 months 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.

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

17 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

This method has been raised and carefully tested before...

13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! You’re really brilliant and a great coder. Khafan Khafan Khafan:)