Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用RMQ怎么要3000+???各位大牛看下我的代码

Posted by mmx21 at 2010-06-06 15:28:09 on Problem 3264
#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;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator