Balanced Lineup POJ-3264(線分樹は一番価値のある水を求める)

3000 ワード
データ構造-線分ツリー
Balanced Lineup
 POJ-3264 
For the daily milking,Farmer John's N cows(1≦ N ≦50,000)alwaysラインナップup in the same order.One day Farmer John decides to organize a game of Ultime Fribee with some of the cows.To keep things simple,he will tare the contigugyou.Holt the from line the.
Farmer John has made a list of Q (1≦ Q ≦200,000)potental groups of cows and their heights(1≦ height ≤1,000,000).For each group,he wants your help to determine the difference in height bertween the shot 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 the height of cow i  リンス N+2. N＋ Q+1:Two integers A and B (1≦A ≦ B ≦ N)representing the range of cows from A ト B inclusive.
Output
Lines 1. Q:Each LINE contains a single integer that is a reponse to a reply and indicates the difference in height between the tallest and shotest 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
n個の数、m個の操作を与え、毎回の操作でx-y区間の最大の差を求める.
構想:線分樹の水の題
ACコード:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define maxn 50005
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define E 1e-8
#define mod 1000000007
#define P pair
#define MID(l,r) (l+(r-l)/2)
#define lson(o) (o<<1) //o*2
#define rson(o) (o<<1|1) //o*2+1
using namespace std;

int a[maxn];
int ql,qr; //    [ql,qr]
int ans_max,ans_min;

struct node
{
    int l,r,mmin,mmax;
}tree[maxn<<2];
void build(int o,int l,int r)
{
    tree[o].l = l;
    tree[o].r = r;
    if(l==r){
        tree[o].mmax = tree[o].mmin = a[l];
        return ;
    }
    int m = MID(l,r);
    int lc = lson(o),rc = rson(o);
    build(lc,l,m);
    build(rc,m+1,r);
    tree[o].mmax = max(tree[lc].mmax,tree[rc].mmax);
    tree[o].mmin = min(tree[lc].mmin,tree[rc].mmin);
}
void query_init()
{
    ans_max = -INF;
    ans_min =  INF;
}
void query(int o)
{
    if(ql<=tree[o].l&& qr>=tree[o].r){ //[L, R]   [ql, qr]   
        ans_max = max(ans_max,tree[o].mmax);
        ans_min = min(ans_min,tree[o].mmin);
        return ;
    }
    int m =MID(tree[o].l,tree[o].r);
    if(ql<=m) query(lson(o));
    if(qr>m)  query(rson(o));
}
int main()
{
    int n,m,x,y;
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        build(1,1,n);
        while(m--){
            scanf("%d %d",&x,&y);
            ql = x;
            qr = y;
            query_init();
            query(1);
            printf("%d
",ans_max-ans_min);
        }
    }
    return 0;
}
poj 2406連続サブストリング