宇宙超究极无敌逆天超级max鸡心
2025-05-17 14:24:50
发布于：北京
12阅读
0回复
0点赞
[【倍增法】区间最值差]
题目描述
询问对于 n 个数中，指定 [L,R] 区间中的最大最小值的差值。
提示
说明/提示
数据范围：
1≤n≤5×104
1≤q≤1.8×105
1≤a**i≤106,1≤i≤n
样例说明：
样例一解释：
区间 [1,5] 的最大值为 7，最小值为 1，最大值减最小值为 7−1=6.
区间 [4,6] 的最大值为 5，最小值为 2，最大值减最小值为 5−2=3.
区间 [2,2] 的最大值为 7，最小值为 7，最大值减最小值为 7−7=0.
样例二解释：
在序列中，只有一个数字 10。
对于询问区间 [1,1]，这个区间只包括数字 10。
因为区间内只有一个数字，所以最大值和最小值都是 10。
最大值减去最小值的差为：10−10=0。
样例三解释：
序列中的所有数字都是 4。
对于第一个询问区间 [1,5]，包含的数字都是 4。
最大值为 4，最小值为 4。
最大值减去最小值的差为：4−4=0。
对于第二个询问区间 [2,4]，同样包含的数字也是 4。
最大值为 4，最小值为 4。
最大值减去最小值的差为：4−4=0。
样例四解释：
整个序列是 [3,1,4,1,5,9]。
对于询问区间 [1,6]，我们取整个序列。
最大值是 9，最小值是 1。
最大值减去最小值的差为：9−1=8。
输入格式
第一行两个整数 n,q 分别表示有 n 个整数和 q 次询问。
第二行开始的 n 行，每行一个整数，表示序列数
最后 q 行每行两个整数 L，R
输出格式
共 q 行输出，每行一个对应的 [L,R] 区间的最大最小差值。
样例组
输入#1
6 3
1
7
3
4
2
5
1 5
4 6
2 2
输出#1
6
3
0
输入#2
1 1
10
1 1
输出#2
0
输入#3
5 2
4
4
4
4
4
1 5
2 4
输出#3
0
0
输入#4
6 1
3
1
4
1
5
9
1 6
输出#4
8
有帮助，赞一个