竹園論壇

標題: d539 - 區間 MAX [打印本頁]

作者: Sylveon 時間: 2014-4-17 15:42
標題: d539 - 區間 MAX
原文：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));
      }
}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)