NEU 1253 线段树

题目描述：

   Do you know LiuJishou? He is a man who is famous of evaluting netizens' appearance on Sina Weibo. One day, LZ wants to simulate LiuJishou and he evalutes N(1<=N<=50,000) girls appearance. The girls are numbered from 1 to N and LZ gives each girl a score(1<=score<=1,000,000).

    LZ is a shy man and he isn't willing to tell his friends the scores of the girls directly, but LZ allows his friend askes him Q (1<=Q<=200,000) questions. Each question has two integers A and B. LZ will tell his friend the difference between the heightest score and the lowest score in the girls whose are numbered from A to B.

    简单的并查集，记录下最小跟最大就OK 了。

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
#define N 50010
 
typedef struct{
    long l,r,max_num,low_num;   
}Node;
long score[N];
long n,q;
Node node[3*N];
long max(long a,long b){
    return a > b? a:b;
}
long min(long a ,long b){
    return a < b?a:b;
}
void init(){
    memset(node,0,sizeof(node));
    memset(score,0,sizeof(node));
}
void Build(long left,long right,int t){
    long mid = (left+right)/2;
    node[t].l = left;
    node[t].r = right;
    if(left == right){
        node[t].low_num = node[t].max_num = score[left];
    }else{
        Build(left,mid,t*2);
        Build(mid+1,right,t*2+1);
        node[t].low_num = min(node[t*2].low_num,node[t*2+1].low_num);
        node[t].max_num = max(node[t*2].max_num,node[t*2+1].max_num);
    }
}
long Query(long left,long right,long t,int flag){
    long mid;
    if(left==node[t].l && right == node[t].r)
        if(flag == 0)
            return node[t].low_num;
        else
            return node[t].max_num;
    if(right<=node[t*2].r)
        return Query(left,right,t*2,flag);
    if(left >= node[t*2+1].l)
        return Query(left,right,t*2+1,flag);
    mid = (node[t].l+node[t].r)/2;
    if(flag == 1)
        return max(Query(left,mid,t*2,1),Query(mid+1,right,t*2+1,1));
    else
        return min(Query(left,mid,t*2,0),Query(mid+1,right,t*2+1,0));
}
int main(){
    int iCase;
    long i,k;
    long a,b;
    scanf("%d",&iCase);
    for(k = 1;k <= iCase;k++){
        //init();
 
        scanf("%ld %ld",&n,&q);
        for(i = 1;i <= n;i++)
            scanf("%ld",&score[i]);
        Build(1,n,1);
        printf("Test case #%d:\n",k);
        for(i = 0;i < q;i++){
            scanf("%ld %ld",&a,&b);
            printf("%ld\n",Query(a,b,1,1) - Query(a,b,1,0));
        }
    }
    return 0;
}
/**************************************************************
    Problem: 1253
    User: ipqhjjybj
    Language: C++
    Result: 正确
    Time:216 ms
    Memory:3320 kb
****************************************************************/