记录编号	38501	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	1.582 s
提交时间	2012-04-19 21:29:03	内存使用	3.32 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = ~0u>>2;
int n, q, a, b, c;
struct node {
    int l, r, x, y;
} T[200000];
void Build(int l, int r, int p) {
    node t = {l, r, 0, INF};
    T[p] = t;
    if(l < r) {
        Build(l, (l + r) / 2, p * 2);
        Build((l + r) / 2 + 1, r, p * 2 + 1);
    }
}
void Insert(int x, int y, int p) {
    T[p].x = max(T[p].x, x), T[p].y = min(T[p].y, x);
    if(T[p].l != T[p].r) {
        if(y <= (T[p].l + T[p].r) / 2)
            Insert(x, y, p * 2);
        else
            Insert(x, y, p * 2 + 1);
    }
}
void Query(int l, int r, int &x, int &y, int p) {
    if(l <= T[p].l && T[p].r <= r) {
        x = T[p].x, y = T[p].y;
        return;
    } int lx = 0, ly = INF, rx = 0, ry = INF;
    if(l <= (T[p].l + T[p].r) / 2)
        Query(l, r, lx, ly, p * 2);
    if(r > (T[p].l + T[p].r) / 2)
        Query(l, r, rx, ry, p * 2 + 1);
    x = max(lx, rx), y = min(ly, ry);
}
int main() {
    freopen("lineup.in", "r", stdin);
    freopen("lineup.out", "w", stdout);
    scanf("%d %d", &n, &q);
    Build(1, n, 1);
    for(int i=1; i<=n; i++) {
        scanf("%d", &c);
        Insert(c, i, 1);
    }
    for(int i=1; i<=q; i++) {
        scanf("%d %d", &a, &b);
        int x = 0, y = INF;
        Query(a, b, x, y, 1);
        printf("%d\n", x - y);
    }
    return 0;
}