Blog·Tanky WooABOUTRSS

POJ 3264 Balanced Lineup

24 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门: http://162.105.81.212/JudgeOnline/problem?id=3264

线段树,Segment Tree。

资料

线段树(Segment Tree)讲解: http://www.wutianqi.com/?p=1140

// Author: Tanky Woo
// www.wutianqi.com
// POJ 3264
// Segment, RMQ

#include 
using namespace std;
const int MAX = 50001;
const int INF = 100000000;

int height[MAX];
typedef struct node{
    int lc, rc, _min, _max;  //左端点,右端点,区间中的最小值,最大值
}Segment;

Segment seg[3*MAX];  // 开三倍大小的空间

// u代表完全二叉树的第u个,所以第u个的左子树是第2*u个,右子树是2*u+1个
void createSeg(int u, int left, int right)
{
    seg[u].lc = left;
    seg[u].rc = right;
    if(left == right) 
    {
        seg[u]._min = seg[u]._max = height[left];
        return;
    }
    int mid = (left+right)/2;
    createSeg(u+u, left, mid);
    createSeg(u+u+1, mid+1, right);
             //求区间最小值,最大值
    seg[u]._min = (seg[u+u]._minseg[u+u+1]._max? seg[u+u]._max:seg[u+u+1]._max);
}

int begin, end;

void findSeg(int u, int &min;_num, int &max;_num)
{
             // 如果区间在所求范围内,给出区间的最小值,最大值
    if(begin<=seg[u].lc && seg[u].rc<=end)
    {
        if(seg[u]._min < min_num)
            min_num = seg[u]._min;
        if(seg[u]._max > max_num)
            max_num = seg[u]._max;
    }
             // 否则,缩小范围,求出相应区间的最小值,最大值
    else
    {
        int mid = (seg[u].lc+seg[u].rc)/2;
        if(mid >= begin)
            findSeg(u+u, min_num, max_num);  //去左区间查找
        if(mid+1 <= end)
            findSeg(u+u+1, min_num, max_num);   //去右区间查找
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int i, j, N, Q, imin, imax;
    while(scanf("%d %d", &N;, &Q;) != EOF)
    {
        for(int i=1; i<=N; ++i)
            scanf("%d", &height;[i]);
        createSeg(1, 1, N);
        while(Q--)
        {
            scanf("%d %d", &begin;, &end;);
            imin = INF;
            imax = -INF;
            findSeg(1, imin, imax);
            printf("%d\n", imax - imin);
        }
    }
    return 0;
}