G - Balanced Lineup

POJ - 3264

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 50010

using namespace std;

int n,q;

struct  nond{

    int l,r,min,max;

}tree[MAXN*];

void up(int now){

    tree[now].max=max(tree[now*].max,tree[now*+].max);

    tree[now].min=min(tree[now*].min,tree[now*+].min);

    return ;

}

void build(int now,int l,int r){

    tree[now].l=l;tree[now].r=r;

    if(tree[now].l==tree[now].r){

        scanf("%d",&tree[now].max);

        tree[now].min=tree[now].max;

        return ;

    }

    int mid=(tree[now].l+tree[now].r)/;

    build(now*,l,mid);

    build(now*+,mid+,r);

    up(now);

}

int querymax(int now,int l,int r){

    if(tree[now].l==l&&tree[now].r==r)

        return  tree[now].max;

    int mid=(tree[now].l+tree[now].r)/;

    if(r<=mid)    return querymax(now*,l,r);

    else if(l>mid)    return querymax(now*+,l,r);

    else    return max(querymax(now*,l,mid),querymax(now*+,mid+,r));

}

int querymin(int now,int l,int r){

    if(tree[now].l==l&&tree[now].r==r)

        return tree[now].min;

    int mid=(tree[now].l+tree[now].r)/;

    if(r<=mid)    return querymin(now*,l,r);

    else if(l>mid)    return querymin(now*+,l,r);

    else return min(querymin(now*,l,mid),querymin(now*+,mid+,r));

}

int main(){

    scanf("%d%d",&n,&q);

    build(,,n);

    for(int i=;i<=q;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        printf("%d\n",querymax(,x,y)-querymin(,x,y));

    }

}