#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	int N, Q;
	cin >> N >> Q;
	int *cow = new int[N + 1];
	int i, j;
	for (i = 1; i <= N; ++i) cin >> cow[i];
//	int Fmin[50001][50001],Fmax[50001][50001];
	int **Fmin = new int*[N + 1];
	for (i = 0; i <= N; ++i) Fmin[i] = new int[17];
	int **Fmax = new int*[N + 1];
	for (i = 0; i <= N; ++i) Fmax[i] = new int[17];
	for(i = 1; i <= N; ++i)
	{
		Fmin[i][0] = cow[i];
		Fmax[i][0] = cow[i];
	}
	for (j = 1; j <= 16; ++j)
	{
		for (i = 1; i <= N; ++i)
		{
			if (i + (1 << j) - 1 <= N)
			{
				Fmin[i][j] = min(Fmin[i][j - 1], Fmin[i + (1 << (j - 1))][j - 1]);
				Fmax[i][j] = max(Fmax[i][j - 1], Fmax[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	int ii, low, high;
	for (ii = 0; ii < Q; ++ii)
	{
		cin >> low >> high;
		int k = int(log(floor(high - low + 1.0))/log(2.0));
		int mymin = min(Fmin[low][k], Fmin[high - (1<<k) + 1][k]), mymax = max(Fmax[low][k], Fmax[high - (1<<k) + 1][k]);
		cout << mymax - mymin << endl;
	}

	delete []cow;
	for (i = 0; i <= N; ++i)
	{
		delete []Fmin[i];
		delete []Fmax[i];
	}
	delete []Fmin;
	delete []Fmax;
	return 0;
}
谢谢。。bow

• Re:用的RMQ，为什么TLE啊。。。。 (760) cww970329 2015-10-08 14:44:01
  • 好多人写线段树，用ST好快的，，，， (95) cww970329 2015-10-08 14:45:52