区间最值问题。

问区间最值，但不存在修改的操作。

$ST$ 表（倍增）：支持查询任意区间 $[l, r]$，但是不支持修改。

查询复杂度 $O(1)$。

建表复杂度 $O(nlogn)$。

$ST$ 表的本质是动态对话求区间最值。

1. 状态：$dp[i][j]$ 以 $i$ 为起点长度为 $2^j$ 的区间最值 $min[i, i + 2 ^ j -1]$。

2. 状态转移方程：$dp[i][j] = min(dp[i][j - 1], dp[i + 2 ^ {j - 1}][j - 1])$。

3. 初始化：$dp[i][0] = a[i]$。

4. 对于任意区间如何查询。

$[l, r]$ 长度为 $len = r - l + 1$。

先求出最大的 $2^i \le len$。

$min(dp[l][i], dp[r - 2^i + 1][i])$

void init() {
	for (int j = 1; (1 << j) <= n; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int query(int l, int r) {
	int i = (int)(log2(r - l + 1));
	return max(dp[l][i], dp[r - (1 << i) + 1][i]);
}
	
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
	    cin >> a[i];
	    dp[i][0] = a[i];
    }
    init();
    while (m--) {
	    int l, r;
	    cin >> l >> r;
	    cout << query(l, r) << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
int a[N], dp[N][21];
int n, m;

inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int query(int l, int r) {
    int i = log2(r - l + 1);
    return max(dp[l][i],  dp[r - (1 << i) + 1][i]);
}

int main() {
	n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        dp[i][0] = a[i];
    }
    for (int j = 1; j <= 21; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
    while (m--) {
        int l, r;
        l = read(), r = read();
        cout << query(l, r) << "\n";
    }
    return 0;
}