d539 - 區間 MAX

Sylveon

原文：http://zerojudge.tw/ShowProblem?problemid=d539
AC   ：http://zerojudge.tw/Submissions?problemid=d539&account=lfs92002
ACCODE：http://ideone.com/hNLD12

區間最大值，裸RMQ問題，用個線段樹就能無CE無DBG無壓力輕鬆AC。

/**********************************************************************************/
/*  Problem: d539 "區間 MAX" from RMQ                                           */
/*  Language: CPP (817 Bytes)                                                     */
/*  Result: AC(0.5s, 8.2MB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2014-04-17 15:31:11                                       */
/**********************************************************************************/


#include<cstdio>
#include<algorithm>
using namespace std;

#define rmq 1,N,0
int data[500000*4];
int N,M,in;

void update(int id,int v,int L,int R,int i)
{
        if(L==R){
                data[i]=v;
                return;
        }
        int M=(L+R)/2;
        if(id<=M)update(id,v,L  ,M,i*2+1);
        else         update(id,v,M+1,R,i*2+2);
        data[i]=max(data[i*2+1],data[i*2+2]);
}
int find(int l,int r,int L,int R,int i)
{
        if(L==l&&R==r)return data[i];
        int M=(L+R)/2;
        if(r<=M)return find(l,r,L  ,M,i*2+1);
        if(M< l)return find(l,r,M+1,R,i*2+2);
        return max(        find(l  ,M,L  ,M,i*2+1),
                                find(M+1,r,M+1,R,i*2+2));
}
int main()
{
        int a,b;
        scanf("%d",&N);
        for(int i=1;i<=N;++i){
                scanf("%d",&in);
                update(i,in,rmq);
        }
        scanf("%d",&M);
        while(M--)
        {
                scanf("%d%d",&a,&b);
                if(a>b)swap(a,b);
                printf("%d\n",find(a,b,rmq));
        }
}