poj_3264 Balanced Lineup

Balanced Lineup

Time Limit: 5000MS	Memory Limit: 65536K
Total Submissions: 23380	Accepted: 10882
Case Time Limit: 2000MS

题目链接：http://poj.org/problem?id=3264

Description

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000)always line up in the same order. One day Farmer John decides to organize agame of Ultimate Frisbee with some of the cows. To keep things simple, he willtake a contiguous range of cows from the milking lineup to play the game.However, for all the cows to have fun they should not differ too much inheight.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potentialgroups of cows and their heights (1 ≤ height ≤ 1,000,000). For eachgroup, he wants your help to determine the difference in height between theshortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is theheight of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A≤ B ≤ N), representing the range of cows from A to Binclusive.

Output

Lines 1..Q: Each line contains a single integerthat is a response to a reply and indicates the difference in height betweenthe tallest and shortest cow in the range.

Sample Input

6 3

1

7

3

4

2

5

1 5

4 6

2 2

Sample Output

6

3

0

Source

USACO 2007 JanuarySilver

解题思路：

这个题目可以用线段树来做，只有两个操作，第一个建立树，第二个查询线段区间即可。

代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#define N 50005
#define Q 200005
using namespace std;
struct segment
{
    int left;
    int right;
    int max;
    int min;
    int value;
};

int n,q;
int high;
segment seg[N*4];
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

int min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}
void update(int rt)
{
    seg[rt].max=max(seg[rt*2].max,seg[rt*2+1].max);
    seg[rt].min=min(seg[rt*2].min,seg[rt*2+1].min);

}
//建树
void buildTree(int l,int r,int rt)
{
    seg[rt].left=l;
    seg[rt].right=r;
    if(l==r)
    {
        scanf("%d",&high);
        seg[rt].max=seg[rt].min=high;
        return;
    }
    int mid=(l+r)/2;
    buildTree(l,mid,rt*2);
    buildTree(mid+1,r,rt*2+1);
    update(rt);
}

//查询区间a到b中的最大差值
int queryMax(int a,int b,int rt)
{
    if(a==seg[rt].left && b==seg[rt].right)
    {
        return seg[rt].max;
    }
	int res=0;
    int mid=(seg[rt].left+seg[rt].right)/2;
    if(b<=mid)
    {
        res=max(res,queryMax(a,b,rt*2));
    }
    else if(a>mid)
    {
		res=max(res,queryMax(a,b,rt*2+1));
    }
    else
    {
        res=max(res,queryMax(a,mid,rt*2));
		res=max(res,queryMax(mid+1,b,rt*2+1));
    }
	return res;
}

int queryMin(int a,int b,int rt)
{
    if(a==seg[rt].left && b==seg[rt].right)
    {
        return seg[rt].min;
    }
    int mid=(seg[rt].left+seg[rt].right)/2;
	int res=999999999;
    if(b<=mid)
    {
        res=min(res,queryMin(a,b,rt*2));
    }
    else if(a>mid)
    {
		res=min(res,queryMin(a,b,rt*2+1));
    }
    else
    {
        res=min(res,queryMin(a,mid,rt*2));
		res=min(res,queryMin(mid+1,b,rt*2+1));
    }
	return res;
	
}

int main()
{

    int a,b;

    scanf("%d%d",&n,&q);
    buildTree(1,n,1);
    while(q--)
    {
        scanf("%d%d",&a,&b);
        int max = queryMax(a,b,1);
		int min= queryMin(a,b,1);
		int val=max-min;
        printf("%d\n",val);
    }
    return 0;
}