UESTC 1591 An easy problem A【线段树点更新裸题】An easy problem A

Submit Status

N个数排成一列，Q个询问，每次询问一段区间内的数的极差是多少。

第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行，每行两个整数L,R(1≤L≤R≤N)。

对于每个询问输出一行，一个整数表示区间内的极差。

Sample Input

Sample Output

题目链接：http://acm.uestc.edu.cn/#/contest/show/155

分析：线段树点更新裸题，继续复习线段树，这题要算的是极差，只需要建树和查询两部分，无需更新，所以建树的时候只要去求最大值和最小值即可，然后极差一减得出答案！

下面给出AC代码：