记录编号	305497	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	SPA	是否通过	通过
代码语言	C++	运行时间	1.149 s
提交时间	2016-09-10 20:51:23	内存使用	1.60 MiB

#include <stdio.h>

template <typename T> inline void Read(T &num) {
	num = 0; char ch; bool minus = 0;
	while (ch = getchar(), ch < '-' || ch > '9');
	if (ch == '-') minus = 1, ch = getchar();
	while (num = num * 10 + ch - 48, ch = getchar(), ch >= '0' && ch <= '9');
	if (minus) num = -num;
}

#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))

const size_t maxn = 50000 + 10;

class Segment_Tree {
	int n, T[maxn << 2][2];
	int ql, qr, _max, _min;
	
public:
#define ls rt << 1
#define rs rt << 1 | 1

	void BuildTree(int rt, int l, int r) {
		if (l == r) {
			scanf("%d", &T[rt][0]);
			T[rt][1] = T[rt][0];
			return;
		}
		int mid = (l + r) >> 1;
		BuildTree(ls, l, mid); BuildTree(rs, mid + 1, r);
		T[rt][0] = Min(T[ls][0], T[rs][0]);
		T[rt][1] = Max(T[ls][1], T[rs][1]);
	}
	
	void Query(int rt, int l, int r) {
		if (l >= ql && r <= qr) {
			if (T[rt][0] < _min) _min = T[rt][0];
			if (T[rt][1] > _max) _max = T[rt][1];
			return;
		}
		int mid = (l + r) >> 1;
		if (mid >= ql) Query(ls, l, mid);
		if (mid + 1 <= qr) Query(rs, mid + 1, r);
	}
	
	int Query(int l, int r) {
		ql = l; qr = r; _min = 0x7f7f7f7f; _max = -1;
		Query(1, 1, n);
		return _max - _min;
	}
	
#undef ls
#undef rs

	Segment_Tree(int _n): n(_n) {
		_max = -1; _min = 0x7f7f7f7f;
		BuildTree(1, 1, n);
	}
};

#define SUBMIT

int main() {
#ifdef SUBMIT
	freopen("lineup.in", "r", stdin);
	freopen("lineup.out", "w", stdout);
#endif

	int n, q; Read(n); Read(q);
	Segment_Tree tree(n);
	int l, r;
	while (q--) {
		scanf("%d%d", &l, &r);
		printf("%d\n", tree.Query(l ,r));
	}

#ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif
	return 0;
}