#include <iostream>

using namespace std;

typedef struct
{
    int lbound, rbound;
    int left, right;
    int minnum, maxnum;
}TreeNode;

class SegmentTree
{
    public:
        int nodenum;
        TreeNode* tree;
    public:
        SegmentTree ( int );
        void build ( int, int );
        void insert ( int, int );
        void search ( int, int, int);
        virtual ~SegmentTree() {delete[]tree;}
};

//当区间长度小于128时采用顺序查找,以减少递归带来的开销
const int len = 128;
//存储区间权重
int ary[50010];
//最大最小值
int Max;
int Min;

SegmentTree::SegmentTree ( int a )
{
    tree = new TreeNode[2*a+10];
    memset ( tree, 0, sizeof ( TreeNode ) * ( 2*a+10 ) );
    nodenum = 0;
    build ( 1, a );
}

void SegmentTree::build ( int a, int b )
{
    nodenum++;
    int v, mid;
    v = nodenum;
    tree[v].lbound = a;
    tree[v].rbound = b;
    tree[v].minnum = INT_MAX;
    tree[v].maxnum = INT_MIN;
    if ( ( b-a ) >= 1 ){
        mid = (a+b)>>1;
        tree[v].left = nodenum+1;
        build ( a, mid );
        tree[v].right = nodenum+1;
        build ( mid+1, b );
    }
}

//典型的二分插入,中值在左边
void SegmentTree::insert ( int i, int a )
{
    int mid,f;
    f = 1;
    while ( 1 )
    {
        if ( a > tree[f].maxnum )
            tree[f].maxnum = a;
        if ( a < tree[f].minnum )
            tree[f].minnum = a;
        if ( ( tree[f].rbound-tree[f].lbound ) == 0 ) break;
        mid = ( tree[f].lbound+tree[f].rbound ) >>1;
        if ( i > mid ) f = tree[f].right;
        else f = tree[f].left;
    }
}

//顺序查找
void Find ( int s, int e)
{
    int i;
    for ( i = s; i <= e; ++i ){
        if ( ary[i] < Min )
            Min = ary[i];
        if ( ary[i] > Max )
            Max = ary[i];
    }
}

//递归查询
void SegmentTree::search ( int s, int e, int f )
{
    int v, mid;
    v = f;
    //如果此区间的最大最小值不比当前的最大最小值更优, 返回
    if ( Min <= tree[v].minnum && Max >= tree[v].maxnum ) return;
    //如果当前的区间刚好覆盖始点与终点，直接查询
    if ( s == tree[v].lbound && e == tree[v].rbound ){
        if ( Min > tree[v].minnum ) Min = tree[v].minnum;
        if ( Max < tree[v].maxnum ) Max = tree[v].maxnum;
        return;
    }
     //砍掉区间左右两边的区间
    if((s < tree[v].lbound) && ((tree[v].lbound-s) <= len)){
        Find(s, tree[v].lbound-1);
        s = tree[v].lbound;
    }
    if((e > tree[v].rbound) && ((e-tree[v].rbound)<=len)){
        Find(tree[v].rbound+1, e);
        e = tree[v].rbound;
    }

    if ( e-s <= len ) Find( s, e);
    else{
        if ( s == tree[v].lbound && e == tree[v].rbound ){
            if ( Min > tree[v].minnum ) Min = tree[v].minnum;
            if ( Max < tree[v].maxnum ) Max = tree[v].maxnum;
        }
        else{
            mid = ( tree[v].lbound+tree[v].rbound ) >>1;
            //查询的区间在当前结点的左子树上
            if ( e <= mid )
                search ( s, e, tree[v].left);
            //查询的区间在当前结点的右子树上
            else if ( s > mid )
                search ( s, e, tree[v].right);
            //在左右子树上查询
            else{
                search ( s, mid, tree[v].left);
                search ( mid+1, e, tree[v].right);
            }
        }
    }
}

int main ( int argv, char* argc[] )
{
    int vex, opt, i, num;
    int f, s;

    while ( scanf ( "%d%d", &vex, &opt ) != EOF ){
        SegmentTree tree ( vex );
        for ( i = 1; i <= vex; ++i ){
            scanf ( "%d", &num );
            ary[i] = num;
            tree.insert ( i, num );
        }
        for ( i = 0; i < opt; ++i ){
            Min = INT_MAX;
            Max = INT_MIN;
            scanf ( "%d %d", &f, &s );
            if ( s - f <= len ) Find ( f, s);
            else tree.search ( f, s, 1);
            printf ( "%d\n", Max-Min );
        }
    }
    return 0;
}

评论