RMQ_CartesianTree

#include <cstdio>

#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

struct Edge {
    int v;
    Edge* next;
};

const int N = 100010, M = 1000010;

int n, m;
int a[N], stk[N], f[N], rk[N], ver[N];
int lca[M];
bool vis[N];
vector<pair<int, int> > qry[N];
Edge* g[N];

void addEdge(int u, int v);
int find(int x);
void merge(int x, int y);
void dfs(int u);

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int r = 1;
    stk[1] = 1;
    for (int i = 2; i <= n; ++i) {
        int lst = 0;
        while (r > 0 && a[i] > a[stk[r]]) {
            if (lst)
                addEdge(stk[r], lst);
            lst = stk[r];
            --r;
        }
        if (lst)
            addEdge(i, lst);
        stk[++r] = i;
    }
    while (r > 1) {
        addEdge(stk[r - 1], stk[r]);
        --r;
    }
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        qry[u].push_back(make_pair(v, i));
        qry[v].push_back(make_pair(u, i));
    }
    dfs(stk[1]);
    for (int i = 1; i <= m; ++i)
        printf("%d\n", a[lca[i]]);
    return 0;
}

void addEdge(int u, int v) {
    static Edge pool[N];
    static Edge* p = pool;
    ++p;
    p->v = v;
    p->next = g[u];
    g[u] = p;
}

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (rk[x] < rk[y]) {
        f[x] = y;
    } else if (rk[x] > rk[y]) {
        f[y] = x;
    } else {
        f[x] = y;
        ++rk[y];
    }
}

void dfs(int u) {
    vis[u] = true;
    f[u] = u;
    ver[u] = u;
    for (Edge* p = g[u]; p; p = p->next) {
        dfs(p->v);
        merge(u, p->v);
        ver[find(u)] = u;
    }
    for (int i = 0; i < qry[u].size(); ++i)
        if (vis[qry[u][i].first])
            lca[qry[u][i].second] = ver[find(qry[u][i].first)];
}