#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;}

评论