#include "stdio.h"
#include "string.h"
#include "math.h"

#define L 50005
int N,Q;
int A[L];
int M[L][20];
int S[L][20];
#define max( x, y ) ( (x) > (y) ? (x) : (y) )
#define min( x, y ) ( (x) < (y) ? (x) : (y) )

void RMQ()
{
	int i,j;
	for(i=1;i<=N;i++)
	{
		M[i][0]=A[i];
		S[i][0]=A[i];
	}
	for(j=1;(1<<j)<=N;j++)
	{
		for(i=1;i+(1<<j)-1<=N;i++)
		{
			M[i][j]=max(M[i][j-1],M[i+(1<<(j-1))][j-1]);
			S[i][j]=min(S[i][j-1],S[i+(1<<(j-1))][j-1]);
		}
	}
}

int main()
{
	int i,k;
	int a,b;
	memset(M,0,sizeof(M));
	memset(S,0,sizeof(S));
	scanf("%d %d",&N,&Q);
	for(i=1;i<=N;i++)
		scanf("%d",&A[i]);
	RMQ();
	while(Q--)
	{
		scanf("%d %d",&a,&b);
		k=(int)(log((double)(b-a+1))/log(2.0));
		printf("%d\n",max(M[a][k],M[b-(1<<k)+1][k])-min(S[a][k],S[b-(1<<k)+1][k]));
	}
	return 0;
}

• 没问题,正常的都3000+ (935) linusc 2011-01-30 15:04:27