(This blog has been restored as Errichto and some other users had wanted.)

Hi !

Here is some implementation for solving RMQ (Tarjan’s algorithm) (Range Maximum / Minimum Query).

It’s very simple to implement and it’s time complexity is O((n + q)·a(n)), a() stands for Akerman inverse function used in DSU.

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

Solution: We need a array of vectors, called assigned. assigned[r] contains queries that their R is r. When getting queries, push each query in assigned[R]. We need a dsu, first par_i is i. We need a stack, named st.

For i from 0 to n, do:
	While st is not empty and a[st.top] <= a[i]
		Set i parent of st.top in dsu and pop this element from st.
Push i to st
For each query assigned to i
	Answer of this query is a[root of L of this query in DSU].

// God & me
// "Someone like you"?! Unbelievable ... 
#include <bits/stdc++.h>
using namespace std;


const int maxn = 1e5 + 17;
int par[maxn], ans[maxn], n, a[maxn], l[maxn], q;
vector<int> qu[maxn];
int root(int v){
    return par[v] == -1 ? v : par[v] = root(par[v]);
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(par, -1, sizeof par);
    cin >> n;
    for(int i = 0; i < n; i++)  cin >> a[i];
    cin >> q;
    for(int i = 0, r; i < q; i++){
	cin >> l[i] >> r, r--, l[i]--;
	qu[r].push_back(i);
    }
    stack<int> st;
    for(int i = 0; i < n; i++){
	while(st.size() && a[st.top()] <= a[i])
	    par[st.top()] = i, st.pop();
	st.push(i);
	for(auto qi : qu[i])
	    ans[qi] = a[root(l[qi])];
    }
    for(int i = 0; i < q; i++)
	cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

Note that in above code I used path-compression technique for dsu only, size-comparing technique can be used too (but it has lower performance).

It’s obviously true, because each time for any j ≤ i, a[root(j)] is the greatest value in range [j, i].