跑了8616K 2016MS，相当慢，不知道大牛怎么跑3、400MS左右
#include <iostream>
#include <math.h>
using namespace std;
int mx[50001][21];
int mi[50001][21];
int d[50001];
int n;
void rmq_init()
{
int i,j;
for(i=1;i<=n;i++) { mx[i][0]=d[i]; mi[i][0]=d[i]; }
int m=floor(log((double)n)/log(2.0));
for(i=1;i<=m;i++)
for(j=0;j+(1<<(i-1))<=n;j++)
{
mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
}
}
int rmq(int l,int r)
{
int m=floor(log((double)(r-l+1))/log(2.0));
int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
int b=min(mi[l][m],mi[r-(1<<m)+1][m]);
return a-b;
}
int main()
{
int q,l,r,i;
while(scanf("%d%d", &n, &q)!=EOF)
{
for(i=1; i<=n; i++)
scanf("%d", &d[i]);
rmq_init();
while(q--)
{
scanf("%d%d", &l, &r);
printf("%d\n", rmq(l,r));
}
}
return 0;
}
posted on 2010-03-27 02:07
wyiu 阅读(156)
评论(0) 编辑 收藏 引用 所属分类:
POJ