Balanced Lineup
题目链接：
http://poj.org/problem?id=3264
题意：
求区间最大值和最小值的差
题解：
Rmq模板题
代码
#include<stdio.h>
#include<math.h>
const int N=5e4+1;
int dpmax[N][17];
int dpmin[N][17];
int mmax(int x,int y)
{
return x>y?x:y;
}
int mmin(int x,int y)
{
return x<y?x:y;
}
void Make_Rmq(int n,int r[])
{
for(int i=1;i<=n;++i)
{
dpmax[i][0]=r[i];
dpmin[i][0]=r[i];
}
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
{
dpmax[i][j]=mmax(dpmax[i][j-1],dpmax[i+(1<<j-1)][j-1]);
dpmin[i][j]=mmin(dpmin[i][j-1],dpmin[i+(1<<j-1)][j-1]);
}
}
int Get_Rmq(int u,int v)
{
int k=(int)(log(v-u+1.0)/log(2.0));
return mmax(dpmax[u][k],dpmax[v-(1<<k)+1][k])-mmin(dpmin[u][k],dpmin[v-(1<<k)+1][k]);
}
int w[N];
void solve()
{
int n,Q,l,r;
while(~scanf("%d",&n)&&n)
{
scanf("%d",&Q);
for(int i=1;i<=n;++i)
scanf("%d",&w[i]);
Make_Rmq(n,w);
while(Q--)
{
scanf("%d%d",&l,&r);
printf("%d
",Get_Rmq(l,r));
}
}
}
int main()
{
solve();
return 0;
}