引入

现在市面上大多数解决 问题的一般是

• 预处理， 回答的线段树，平衡树。
• 预处理， 回答的 表，猫树。
• 预处理， 回答的分块加 表，这种神仙算法。

这里考虑使用 的 预处理， 回答的算法，这里用求区间最大举例。

Cartesian-tree

对于笛卡尔树，我们可以根据性质，对于一个节点 ，它的子树的任意权值都比 要小，因为笛卡尔树是满足 的性质的，所以节点 一定是管辖的一个连续的区间的。根据笛卡尔树的性质，那么 的最大值就是节点 的 的权值。

tarjan

关于 求 。这里是一种离线算法，总的复杂度为 不考虑并查集的常数。这个的讲解网上很全，我这里抛一个链接。如何用 tarjan 求 LCA 。因此我们就得到了 预处理， 回答询问的方法 。其实如果不会 也可以用其它的方法做到 （例如倍增求 ）或者其它复杂度的算法。

代码

#include<bits/stdc++.h>
using namespace std;
struct Query{int id,pos;};
const int N = 2e6 + 1000, M = 1e5 + 1000;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
vector<Query> q[M];
vector<int> G[M];
int fa[M],vis[M],n,m,root,ans[N],top,val[M],rc[M],lc[M],st[M];
int find(int x) {return fa[x] == x?x:fa[x]=find(fa[x]);}
void dfs(int x,int Fa) {
    for(auto y:G[x]) {
        if(y == Fa) continue;dfs(y,x);fa[y] = x;
    }
    vis[x] = 1;
    for(auto Q:q[x]) {
        if(vis[Q.pos]) ans[Q.id] = find(Q.pos);
    }
}
int main() {
    n = read();m = read();
    for(int i = 1;i <= n;i++) val[i] = read();
    for(int i = 1;i <= n;i++) {
        int k = top;
        while(k && val[i] >= val[st[k]]) k--;
        if(k) rc[st[k]] = i;
        if(k < top) lc[i] = st[k + 1];
        st[++k] = i;top = k;
    }
    root = st[1];
    for(int i = 1;i <= n;i++) {
        int a = lc[i],b = rc[i];
        if(a) G[i].push_back(a);
        if(b) G[i].push_back(b);
    }
    for(int i = 1;i <= m;i++) {
        int a = read(),b = read();
        q[a].push_back((Query){i,b});
        q[b].push_back((Query){i,a});
    }
    for(int i = 1;i <= n;i++) fa[i] = i;
    dfs(root,0);
    for(int i = 1;i <= m;i++) printf("%d\n", val[ans[i]]);
    return 0;
}