POJ3264

/*
算法过程：
1.构建线段树
2.在线段树中插入数据
3.对线段树进行更新（该题无更新操作）和查询
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 0xffffff0;
struct node{
    int l;  //区间左端点
    int r;  //区间右端点
    //下面是特殊设定的数据域
    int minx, maxx; //区间中最高和最矮的奶牛身高
}tree[800010];

int minx = INF;
int maxx = -INF;

// 对区间l,r建立线段树
void build_tree(int i, int l, int r) {
    //节点i的数据域的初始化（即根节点）
    tree[i].l = l;
    tree[i].r = r;
    tree[i].minx = INF;
    tree[i].maxx = -INF;
    if(l != r) {  
        int mid = (l + r) / 2;
        build_tree(2 * i + 1, l, mid);
        build_tree(2 * i + 2, mid + 1, r);
    }
}

void Insert(int root, int i, int h) {
    if(tree[root].l == tree[root].r) {
        tree[root].maxx = tree[root].minx = h;
        return;
    }
    tree[root].minx = min(tree[root].minx, h);
    tree[root].maxx = max(tree[root].maxx, h);
    if(i <= (tree[root].l + tree[root].r) / 2) {
        Insert(2 * root + 1, i, h);
    } else {
        Insert(2 * root + 2, i, h);
    }
}

void query(int root, int a1, int a2) {
    if(tree[root].minx >= minx && tree[root].maxx <= maxx) {
        return;
    }
    if(tree[root].l == a1 && tree[root].r == a2) {
        minx = min(minx, tree[root].minx);
        maxx = max(maxx, tree[root].maxx);
        return;
    }
    int mid = (tree[root].l + tree[root].r) / 2;
    if(a2 <= mid) {
        query(2 * root + 1, a1, a2);
    } else if(a1 > mid) {
        query(2 * root + 2, a1, a2);
    } else {
        query(2 * root + 1, a1, mid);
        query(2 * root + 2, mid + 1, a2);
    }
}
int main () {
    int N, Q;
    scanf("%d%d", &N, &Q);
    build_tree(0, 1, N);
    for(int i = 1; i <= N; ++i) {
        int h;
        scanf("%d", &h);
        Insert(0, i, h);
    }
    while(Q--) {
        int a1, a2;
        scanf("%d%d", &a1, &a2);
        minx = INF;
        maxx = -INF;
        query(0, a1, a2);
        printf("%d\n", maxx - minx);
    }
    return 0;
}