TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原文: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));
}
}
|
|