【模板】ST 表 & RMQ 问题

题目背景

这是一道 ST 表经典题——静态区间最大值

请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 $O(1)$。若使用更高时间复杂度算法不保证能通过。

如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：

inline 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;
}

函数返回值为读入的第一个整数。

快速读入作用仅为加快读入，并非强制使用。

题目描述

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 $N,M$，分别表示数列的长度和询问的个数。

第二行包含 $N$ 个整数（记为 $a_i$），依次表示数列的第 $i$ 项。

接下来 $M$ 行，每行包含两个整数 $l_i,r_i$，表示查询的区间为 $[l_i,r_i]$。

输出格式

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

输入样例 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出样例 #1

9
9
7
7
9
8
7
9

输入样例 #2

1 1
0
1 1

输出样例 #2

0

输入样例 #3

45 31
519992588 818750702 611499839 515589924 599588758 503447854 884795829 827561221 472811323 647744532 599065764 391284929 417426714 50910094 116337146 865633092 499421440 258894752 544362089 849483213 493453075 400896394 285488401 443787503 49369456 879538465 940253718 287876195 953021815 735093834 22834027 389208619 124920014 808563766 495842507 235508913 197043078 716540519 389126238 708326080 41141323 934332245 267449582 400315149 320406825
18 21
28 39
1 30
32 33
19 20
6 9
23 34
43 43
6 8
37 37
24 34
33 42
1 39
42 45
12 32
19 22
30 31
38 38
44 44
26 45
18 44
36 39
30 32
23 37
26 43
38 39
44 45
6 9
17 25
4 20
18 39

输出样例 #3

849483213
953021815
953021815
389208619
849483213
884795829
953021815
267449582
884795829
197043078
953021815
934332245
953021815
934332245
953021815
849483213
735093834
716540519
400315149
953021815
953021815
716540519
735093834
953021815
953021815
716540519
400315149
884795829
849483213
884795829
953021815

数据范围

请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 $O(1)$。

对于 $30\%$ 的数据，满足 $1\le N,M\le 10$。

对于 $70\%$ 的数据，满足 $1\le N,M\le {10}^5$。

对于 $100\%$ 的数据，满足 $1\le N\le {10}^5$，$1\le M\le 2\times{10}^6$，$a_i\in[0,{10}^9]$，$1\le l_i\le r_i\le N$。