Balanced Lineup：线段树：区间最值 / RMQ

不要被线段树这个名字和其长长的代码吓到。

D - Balanced Lineup

Description

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

Sample Output

6
3
0

线段树主要的是个树结构，多用于区间修改，查询。修改查询的时间复杂度都为O（long n），是一个很理想的复杂度。

一般输入数据比较多，所以用cin要关闭流同步，或者用scanf，当然最推荐的还是快读。

/*
				线段树：区间查询最大最小值
*/

#include<iostream>			
#include<algorithm>
using namespace std;
const int maxn = 50020;		//总节点数

struct node {
	int l, r;
	int maxx;				//区间最大值
	int minx;				//区间最小值
}tree[4*maxn];				//总节点数 最坏情况下是4*maxn

int n, m, t;

inline int read() {			//快读
	int i = 0, j = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')j = -1; ch = getchar(); }
	while (ch >= '0'&&ch <= '9') i = i * 10 + ch - '0', ch = getchar();
	return i*j;
}

void buildtree(int p, int l, int r) {		//建树&更新节点
	tree[p].l = l;				//初始化
	tree[p].r = r;				//每个节点的左右区间，就是传入的l，r
	tree[p].maxx = -1;			//把最大值赋值为-1
	tree[p].minx = 1e9;			//给minx赋值一个在题目中最大的值


	if (l == r) {				//l==r  代表是叶子节点 
		tree[p].maxx = tree[p].minx = read();
		return;
	}

	int mid = l + r >> 1;				//不是叶子节点，就把区间分开		左儿子比右儿子多  （1+5）/2=3 ==> [1~3]--[4~5]
	buildtree(p * 2, l, mid);			//左区间树
	buildtree(p * 2+1, mid + 1, r);		//右区间树


	tree[p].maxx = max(tree[p * 2].maxx, tree[p * 2 + 1].maxx);		//节点的最大值，就是两个儿子节点的最大值
	tree[p].minx = min(tree[p * 2].minx, tree[p * 2 + 1].minx);		//同理
}

int findmax(int p, int x, int y)		//查找最大值
{
	if (x<=tree[p].l&&tree[p].r <= y)					//为什么是<=而不是==，这里是与下边匹配的。
		return tree[p].maxx;

	int Max = -1, mid = (tree[p].l + tree[p].r) / 2;
	if (x <= mid) 
		Max = max(Max, findmax(2 * p, x, y));				//搜索左区间，区间范围仍然是x~y，所以上边是<=
	if (y > mid)
		Max = max(Max, findmax(2 * p + 1, x, y));			//搜索右区间。
	return Max;
	
}

int findmin(int p, int x, int y) {		//查找最小值				同查找最大值
	if (tree[p].l >= x&&tree[p].r <= y)							
		return tree[p].minx;
	int Min = 1e9, mid = (tree[p].l + tree[p].r) / 2;
	if (x <= mid)
		Min = min(Min, findmin(p * 2, x, y));
	if (y > mid)														
		Min = min(Min, findmin(p * 2 + 1, x, y));
	return Min;
}

int main() {

	cin >> n >> m;
	
	buildtree(1, 1, n);			//可以把输入放在建树里边，

	int x, y;
	for (int i = 0; i < m; i++) {
		x = read();
		y = read();
		cout << findmax(1, x, y)-findmin(1, x, y) << endl;
	}
	return 0;
}