ST表

虽然ST表不是本题的唯一实现，但是静态RMQ问题ST表是最好写的。

oi-wiki：ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构

O(nlogn)的预处理

我们可以发现区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。

我们定义$f[i][j]$表示从第i个数起连续$2^j-1$个数中的最大值

我们把$f[i][j]$平均分成两段（因为$f[i][j]$一定是偶数个数字），从 $i$ 到 $i+2^{j-1}-1$ 为一段，$i + 2 ^ {j - 1}$ 到 $i + 2 ^ j - 1$为一段(长度都为 $2 ^ {j - 1}$ )。

于是我们得到了状态转移方程 $F[i][j]=max（F[i][j-1], F[i + 2^{j-1}][j-1]）$。

如图：

优秀的O(1)查询 $qwq$

我们思考如何查询 $[l,r]$

可以用与预处理一样的方法

我们依旧定义$f[i][j]$表示从第i个数起连续$2^j-1$个数中的最大值

我们把它分成两部分：$[l,l+2^s-1]$ 与 $[r-2^s+1,r]$，其中 $s=\left\lfloor\log_2(r-l+1)\right\rfloor$。两部分的结果的最大值就是回答。

$\log_2x$可以用cmath的库函数，也可以线性预处理

当$\log_2x$为$\left\lfloor r-l+1\right\rfloor$显然$l$与$r$之间是有交集且不会超范围的。

如图：

$AC code$

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 17 //考虑题目取log2
int fm[maxn][maxm],fn[maxn][maxm],logn[maxn];
int n,m;
void pre() {
	logn[1]=0;
	logn[2]=1;
	for(int i=3; i<maxn; i++)
		logn[i]=logn[i>>1]+1;
}
int read() {
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}//快速读入
int x,y;
int main() {
	n=read(),m=read();
	pre();
	for(int i=1; i<=n; i++){
        fm[i][0]=read();
        fn[i][0]=fm[i][0];// 数据读入
    }
    for (int j = 1; j < maxm; j++)//动态规划预处理得到ST表
		for (int i = 1; i + (1 << j) - 1 <= n; i++){
			fm[i][j] = max(fm[i][j - 1], fm[i + (1 << (j - 1))][j - 1]);
            fn[i][j] = min(fn[i][j - 1], fn[i + (1 << (j - 1))][j - 1]);
    }
    for (int i = 1; i <= m; i++) {
		int x = read(), y = read();
		int s = logn[y - x + 1];//O(1)询问
        int ansm=max(fm[x][s], fm[y - (1 << s) + 1][s]);
        int ansn=min(fn[x][s], fn[y - (1 << s) + 1][s]);
		printf("%d\n", ansm-ansn);
	}
	return 0;
}