C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

poj 3264 Balanced Lineup 解题报告

Posted on 2011-11-28 17:02 C小加 阅读(1524) 评论(0)  编辑 收藏 引用 所属分类: 解题报告
题意:给出一组数,输出区间最大值和最小值的差值
思路:线段树水题。建树的时候直接把最值初始化好,然后直接找最值。1700+ms
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int L(int r){return r<<1;}
inline int R(int r){return (r<<1)+1;}
inline int MID(int l,int r){return (l+r)>>1;}
const int MAXN=50003;
const int INF=0x7fffffff-1;
int ansmax,ansmin;
typedef struct
{
    int left,right;
    int _max,_min;
}Node;
Node tree[MAXN*4];
int arr[MAXN];
void Create(int l,int r,int root)
{
    tree[root].left=l;
    tree[root].right=r;
    if(l==r)
    {
        tree[root]._max=arr[l];
        tree[root]._min=arr[l];
        return;
    }
    int mid=MID(l,r);
    Create(l,mid,L(root));
    Create(mid+1,r,R(root));
    tree[root]._max=max(tree[L(root)]._max,tree[R(root)]._max);
    tree[root]._min=min(tree[L(root)]._min,tree[R(root)]._min);
}
void Solve(int l,int r,int root)
{
    if(tree[root].left==l&&tree[root].right==r)
    {
        ansmax=max(ansmax,tree[root]._max);
        ansmin=min(ansmin,tree[root]._min);
        return;
    }
    if(tree[root].left==tree[root].right) return;
    int mid=MID(tree[root].left,tree[root].right);
    if(l>mid) Solve(l,r,R(root));
    else if(r<=mid) Solve(l,r,L(root));
    else
    {
        Solve(l,mid,L(root));
        Solve(mid+1,r,R(root));
    }
}
int main()
{
    int m,n;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        for(int i=1;i<=m;i++)
        {
            scanf("%d",arr+i);
        }
        Create(1,m,1);
        int tl,tr;
        while(n--)
        {
            ansmax=0;
            ansmin=INF;
            scanf("%d %d",&tl,&tr);
            if(tl==tr)
            {
                printf("0\n");
                continue;
            }
            Solve(tl,tr,1);
            printf("%d\n",ansmax-ansmin);
        }
    }

    return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理