#include <stdio.h>
#include <math.h>
const int MAXN = 50001;
const int MAX = 20;    //log(MAXN) / log(2) + 1;
int num[MAXN];
int fmin[MAX][MAXN], fmax[MAX][MAXN];
int pow2[MAX];
int n, question;

inline int Min(const int &x, const int &y)
{
	return x < y ? x : y;
}

inline int Max(const int &x, const int &y)
{
	return x > y ? x : y;
}

void Init()
{
	int i;
	scanf("%d %d", &n, &question);
	for (i = 1; i <= n; i++)
		scanf("%d", &num[i]);
}

void MakeRMQ()
{
	int i, j;

	for (i = 0; i < MAX; i++)
		pow2[i] = 1 << i;

	for (j = 1; j <= n; j++)
		fmin[0][j] = fmax[0][j] = num[j];
	int m = floor(log((double)n) / log(2.0));
	for (i = 1; i <= m; i++)
		for (j = 1; j <= n - pow2[i] + 1; j++)
		{
			fmin[i][j] = Min(fmin[i - 1][j], fmin[i - 1][j + pow2[i - 1]]);
			fmax[i][j] = Max(fmax[i - 1][j], fmax[i - 1][j + pow2[i - 1]]);
		}
}

int RMQ_Max(int l, int r)
{
	int k = floor(log((double)r - l + 1) / log(2.0));
	return Max(fmax[k][l], fmax[k][r - pow2[k] + 1]);
}

int RMQ_Min(int l, int r)
{
	int k = floor((int)log((double)r - l + 1) / log(2.0));
	return Min(fmin[k][l], fmin[k][r - pow2[k] + 1]);
}

int RMQ(int l, int r)
{
	int k = floor(log((double)r - l + 1) / log(2.0));
	return Max(fmax[k][l], fmax[k][r - pow2[k] + 1]) - Min(fmin[k][l], fmin[k][r - pow2[k] + 1]);
}
void Work()
{
	int i, l, r;
	for (i = 0; i < question; i++)
	{
		scanf("%d %d", &l, &r);
		printf("%d\n", (RMQ_Max(l, r) - RMQ_Min(l, r)));  //这样WA
		printf("%d\n", RMQ(l, r));                        //这样AC
	}
}
int main()
{
	freopen("in3264.txt", "r", stdin);
	Init();
	MakeRMQ();
	Work();
	return 0;
}

• Re:很诡异！！！差不多的写法一个WA一个AC， 不看后悔呀!!!!! (11) sishen007 2009-08-02 16:35:18