#P3865. 【模板】ST 表 & RMQ 问题
【模板】ST 表 & RMQ 问题
P3865 【模板】ST 表 & RMQ 问题
题目描述
给定一个长度为 的数列 ,以及 次询问。每次询问给出一个区间 ,请求出该区间内所有数字的最大值。
输入格式
第一行输入两个整数 $n, m \left(1 \leqq n \leqq 10^5;\ 1 \leqq m \leqq 2 \times 10^6\right)$ 代表数列长度和询问次数。
第二行输入 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 10^9\right)$ 依次代表数列的第 项。
此后 行,第 行输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 次询问的区间。
输出格式
输出 行,第 行输出一个整数,代表第 次询问的答案。
测试样例
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 解释
数列为 ,依次回答每次询问:
询问 ,区间内最大值为 ;
询问 ,区间内最大值为 ;
询问 ,区间内最大值为 ;
询问 ,区间内最大值为 ;
询问 ,区间内最大值为 ;
询问 ,区间内最大值为 ;
询问 ,区间内最大值为 ;
询问 ,区间内最大值为 。
因此依次输出 。
6 5
6 2 8 5 1 9
1 4
2 3
3 6
4 5
1 6
8
8
9
5
9
提示
这是一道 ST 表经典题——静态区间最大值。
请注意最大数据时限只有 秒,数据强度不低,请务必保证你的每次查询复杂度为 。若使用更高时间复杂度的算法,不保证能通过。
如果认为自己的代码时间复杂度正确但仍然超时,可以尝试使用快速读入:
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;
}
函数返回值为读入的第一个整数。快速读入的作用仅为加快读入,并非强制使用。
对于 的数据,;
对于 的数据,;
对于 的数据,,,,。