POJ 3264

#include<iostream>
#include<cstdio>
#include<algorithm>


using namespace std;

const int N = 50010;
const int INF = 0x3f3f3f3f;

int rmin = INF, rmax = -INF;//用全局变量来储存查询区域的最值

struct Node
{

    int left, right;
    int maxi, mini;
    int mid()
    {
        return (left+right)>>1;
    }

} tree[4*N];

void build(int root, int l, int r)//建树过程
{

    tree[root].left = l;
    tree[root].right = r;
    tree[root].mini = INF;
    tree[root].maxi = -INF;

    if(l == r)
    {
        return;
    }
    else
    {
        build(2*root, l, tree[root].mid());
        build(2*root+1, tree[root].mid()+1, r);
    }

}

void minsert(int root, int pose, int value)
{

    if( tree[root].left == tree[root].right )//找到位置插入
    {

       tree[root].mini = tree[root].maxi = value;
        return;

    }

    tree[root].mini = min(tree[root].mini, value);
    tree[root].maxi = max(tree[root].maxi, value);
    if(pose <= tree[root].mid())
        minsert(root*2, pose, value);
    else
        minsert(root*2 + 1, pose, value);

}

void query(int root, int s, int e)
{

    if(tree[root].mini > rmin && tree[root].maxi < rmax)/*若某树的最小值大于所求的最小值，则它的子树的最小值必定大于所求最小值，最大值同理*/
        return;
    if(tree[root].left == s && tree[root].right == e)
    {

        rmin = min(rmin, tree[root].mini);
        rmax = max(rmax, tree[root].maxi);
        return;
    }
    if(e <= tree[root].mid())
    {
        query(root*2, s,e);
    }
    else if(s > tree[root].mid())
    {
        query(root*2+1, s, e);
    }
    else
    {
        query(root*2, s, tree[root].mid());
        query(root*2+1, tree[root].mid() + 1, e);
    }

}

int main()
{

    int n, q, he, a, b;
    scanf("%d %d", &n, &q);
    {
        build(1,1,n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &he);
            minsert(1, i, he);
        }
        while(q--)
        {
            scanf("%d %d", &a, &b);
            rmin = INF;
            rmax = -INF;
            query(0, a, b);
            printf("%d
",rmax-rmin);

        }
    }
    return 0;

}