POJ3264 区间最大减区间最小

区间操作，线段树和打表都行，主要打表的操作老是加一和减一搞晕，重写一遍找找感觉

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 5e4+10;
int n,m,a[maxn];
int dp1[maxn][80],dp2[maxn][80];
void RMQ()
{
	for(int i = 1; i <= n; ++i)dp1[i][0]=dp2[i][0]=a[i];
	for(int len = 1;(1<<len)<=n; ++len)
	for(int i = 1; i+(1<<len)-1<=n; ++i)
	{
		dp1[i][len]=max(dp1[i][len-1],dp1[i+(1<<(len-1))][len-1]);
		dp2[i][len]=min(dp2[i][len-1],dp2[i+(1<<(len-1))][len-1]);
	}
}
int query(int l,int r,int op)
{
	int len = r-l+1,i = 0;
	while((1<<i)<=len) i++;i--;
	if(op) return max(dp1[l][i],dp1[r-(1<<i)+1][i]);
	return min(dp2[l][i],dp2[r-(1<<i)+1][i]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
	RMQ();
	int l,r;
	while(m--)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",query(l,r,1)-query(l,r,0));
	}
}