学步园

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=119
题目分析：
这道题用的RMQ算法(range maximum/minimum query)
。这里做了几点优化。
1）定义dpMax和dpMin时，为什么17写在前面，因为内存中数据是按行连续的存的，所以初始化dpMax[0]和dpMin[0]相关数据时，可以直接用memcpy。
2）所有的求2的方幂的操作都是用的位运算，这样会比较快。在求比一个数小的最大的二的方幂，也就是这个数的最左边的1，没有用库函数。还没有研究过到底哪个快，但感觉用库函数可能不会比这个方式快吧？

#include<stdio.h>
#include<string.h>

const int N = 100001;
int arr[N];
//因为10^5约等于2^16.6
int dpMax[17][N];
int dpMin[17][N];

int GetBit(unsigned int x)
{//最高位的1的位置
	int count = -1;
	while(x)
	{
		x >>= 1;
		++count;
	}
	return count;
}

inline int max(const int a, const int b)
{
	return a > b ? a : b;
}

inline int min(const int a, const int b)
{
	return a < b ? a : b;
}

void RMQ(int n)
{
	int k = GetBit(n);
	memcpy(&dpMax[0][1], &arr[1], n * sizeof(int));
	memcpy(&dpMin[0][1], &arr[1], n * sizeof(int));
	for(int j = 1; j <= k; ++j)//步长
	{
		for(int i = 1; i <= n; ++i)
		{
			if(i + (1 << j) - 1 <= n)
			{
				dpMax[j][i] = max(dpMax[j - 1][i], dpMax[j - 1][i + (1 << (j - 1))]);
				dpMin[j][i] = min(dpMin[j - 1][i], dpMin[j - 1][i + (1 << (j - 1))]);
			}
		}
	}
}

int main()
{
	int n,m,i;
	int a,b;
	int k,Max,Min;
	while(scanf("%d %d", &n, &m) != EOF)
	{
		for(i = 1; i <= n; ++i)
			scanf("%d", &arr[i]);
		RMQ(n);
		for(i = 0; i < m; ++i)
		{
			scanf("%d %d", &a, &b);
			k = GetBit(b - a + 1);
			Max = max(dpMax[k][a], dpMax[k][b - (1 << k) + 1]);
			Min = min(dpMin[k][a], dpMin[k][b - (1 << k) + 1]);
			printf("%d\n", Max - Min);
		}
	}
	return 0;
}