我需要 scanf！

scanf，我在这里！

scanf，快帮帮我！

致敬传奇 49 TLE。

题意

不多赘述

思路

标题都说了是 ST 表模板，那我介绍一下 ST 表咋做。

这是一个数列

现在我们要求最大值，直接遍历整个数组就能找到。但如果要寻找不同区间（比如 [1,4]，[3,6]）的最大值，一遍一遍遍历就太慢了，于是你想到可以两个两个存最大值。

这时你想到应该再三个三个存下去，但是这样空间复杂度是 $n^2$，直接 CE。这时你又想到每次记 $2^n$ 个，这样空间复杂度就是 $nlogn$ 了。

可是该如何建表呢？

每次都从原数组取肯定不行，耗时更多。那我们就从上一列的结果取。拿 $j=2$ 举例，$st_{i,j}=max(st_{i,j-1},st_{i+2^j,j-1})$，$st_{i,j}$ 刚好对应了原数组的 4 个（$2^j$ 个）数的最大值（可以拿下表对照）。

这是 ST 表

i\j | 0  | 1  | 2  |
----+---------------
1   | 5  | 5  | 7  |
2   | 3  | 7  | 12 |
3   | 7  | 7  | 12 |
4   | 2  | 12 |    |
5   | 12 | 12 |    |
6   | 1  |    |    |

ST 表的代码重要的是“推”，不是“记”，在考场上要自己推出来这个表来写代码，而不是直接套模板。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,LOG2N = 20;
int a[N][LOG2N],Log2[N];
int main(int argc, char **argv){
	int n,m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		scanf("%d",a[i]);
	}
	for (int i = 2;i <= n;i++){
		Log2[i] = Log2[i >> 1] + 1;
	}
	for (int j = 1;j <= Log2[n];j++){
		for (int i = 1;i <= n - (1 << j) + 1;i++){
			a[i][j] = max(a[i][j - 1],a[i + (1 << (j - 1))][j - 1]);
		}
	}
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		int k = Log2[r - l + 1];
		printf("%d\n",max(a[l][k],a[r - (1 << k) + 1][k]));
	}
	return 0;
}