#P3865. 【模板】ST 表 & RMQ 问题

【模板】ST 表 & RMQ 问题

P3865 【模板】ST 表 & RMQ 问题

题目描述

\hspace{15pt}给定一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及 mm 次询问。每次询问给出一个区间 [li,ri][l_i, r_i],请求出该区间内所有数字的最大值。

输入格式

\hspace{15pt}第一行输入两个整数 $n, m \left(1 \leqq n \leqq 10^5;\ 1 \leqq m \leqq 2 \times 10^6\right)$ 代表数列长度和询问次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 10^9\right)$ 依次代表数列的第 ii 项。

\hspace{15pt}此后 mm 行,第 ii 行输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 ii 次询问的区间。

输出格式

\hspace{15pt}输出 mm 行,第 ii 行输出一个整数,代表第 ii 次询问的答案。

测试样例

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
9
9
7
7
9
8
7
9

样例 1 解释

\hspace{15pt}数列为 {9,3,1,7,5,6,0,8}\{9,3,1,7,5,6,0,8\},依次回答每次询问:

∙ \hspace{23pt}\bullet\,询问 [1,6][1,6],区间内最大值为 99;

∙ \hspace{23pt}\bullet\,询问 [1,5][1,5],区间内最大值为 99;

∙ \hspace{23pt}\bullet\,询问 [2,7][2,7],区间内最大值为 77;

∙ \hspace{23pt}\bullet\,询问 [2,6][2,6],区间内最大值为 77;

∙ \hspace{23pt}\bullet\,询问 [1,8][1,8],区间内最大值为 99;

∙ \hspace{23pt}\bullet\,询问 [4,8][4,8],区间内最大值为 88;

∙ \hspace{23pt}\bullet\,询问 [3,7][3,7],区间内最大值为 77;

∙ \hspace{23pt}\bullet\,询问 [1,8][1,8],区间内最大值为 99。

\hspace{15pt}因此依次输出 9,9,7,7,9,8,7,99,9,7,7,9,8,7,9。

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

提示

\hspace{15pt}这是一道 ST 表经典题——静态区间最大值。

\hspace{15pt}请注意最大数据时限只有 0.80.8 秒,数据强度不低,请务必保证你的每次查询复杂度为 O(1)O(1)。若使用更高时间复杂度的算法,不保证能通过。

\hspace{15pt}如果认为自己的代码时间复杂度正确但仍然超时,可以尝试使用快速读入:

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

\hspace{15pt}函数返回值为读入的第一个整数。快速读入的作用仅为加快读入,并非强制使用。

\hspace{15pt}对于 30%30\% 的数据,1≦n,m≦101 \leqq n, m \leqq 10;

\hspace{15pt}对于 70%70\% 的数据,1≦n,m≦1051 \leqq n, m \leqq 10^5;

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1051 \leqq n \leqq 10^5,1≦m≦2×1061 \leqq m \leqq 2 \times 10^6,0≦ai≦1090 \leqq a_i \leqq 10^9,1≦li≦ri≦n1 \leqq l_i \leqq r_i \leqq n。