记录编号	405807	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.527 s
提交时间	2017-05-17 13:14:33	内存使用	0.50 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 5e4 + 10;

inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp)) tmp = getchar();
	while(isdigit(tmp)) 
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct DATA{ 
	int lh, hh;

	DATA(){;}
	DATA(int a, int b){
		lh = a, hh = b;
	}

	void put(void) const {
		printf("%d\n", hh - lh);
	}
};

struct NODE{ 
	DATA val;
	NODE *ls, *rs;

	NODE(){
		ls = rs = NULL;
	}
};

inline DATA cmp(const DATA& a, const DATA& b);
NODE* build(int l, int r);
DATA query(NODE *now, int l, int r, int L, int R);

int h[MAXN];
int N, Q;
NODE *root;

int main(){ 
#ifndef LOCAL
	freopen("lineup.in", "r", stdin);
	freopen("lineup.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	N = in(), Q = in();
	for(int i = 1; i <= N; ++i) h[i] = in();

	root = build(1, N);

	for(int i = 1, l, r; i <= Q; ++i){ 
		l = in(), r = in();
		query(root, l, r, 1, N).put();
	}

	return 0;
}

inline DATA cmp(const DATA& a, const DATA& b){ 
	return DATA(min(a.lh, b.lh), max(a.hh, b.hh));
}

NODE* build(int l, int r){
	NODE *p = new NODE();

	if(l == r) p->val = DATA(h[l], h[l]);
	else{ 
		int mid = (l + r) >> 1;
		p->ls = build(l, mid);
		p->rs = build(mid + 1, r);
		p->val = cmp(p->ls->val, p->rs->val);
	}

	return p;
}

DATA query(NODE *now, int l, int r, int L, int R){ 
	if(l == L && r == R) return now->val;

	int mid = (L + R) >> 1;
	if(r <= mid) return query(now->ls, l, r, L, mid);
	if(mid < l) return query(now->rs, l, r, mid + 1, R);

	return cmp(query(now->ls, l, mid, L, mid), query(now->rs, mid + 1, r, mid + 1, R));
}