问题1254--区间最值问题

1254: 区间最值问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 162  解决: 91
[提交] [状态] [讨论版] [命题人:]

题目描述

本题很简单,给定n,然后输入n个整数,然后给定m,输入m个询问,对于每个询问,求区间[a, b]内最大值与最小值的差值。

估计很多同学看完就想到可以用万能的线段树在解此题了,不过罗老师告诉大家,对于此类问题,还有一个叫RMQ的方法哦!

当然不管用什么方法,希望你先把它解决了吧!

输入

输入n, m

接下来n行,每行输入一个整数vi

接下来m行,每行输入两个整数a,b,表示询问[a, b]

输出

对于每组询问,求区间[a, b]内,最大值与最小值的差值。

样例输入 Copy

6 3
1
7
3
4
2
5
1 5
4 6
2 2

样例输出 Copy

6
3
0

提示

【数据规模和约定】

1<=N<=50000, 1<=m<=100000, 0<=vi<=1000000

来源/分类

RMQ