P2880 平衡的阵容

　　在这里介绍一种新的算法（十分优秀）：ST表

　　这个算法，其实就是求一段区间内最大值或者最小值是多少，当然就是一种降低时间复杂度的优化。

　　显然线段树是不行的（复杂度太高O（mlog_n）），所以妄想写线段树的人就放弃吧~      ：3 

　　那么首先明白概念性解释，对于dp[i][j]，意思是以i为起点，长度为2^j的区间里的最大值（注意我的表述）。

　　那么就很简单了，主要思想就是每次一分为二，分别求最大值，再求整个的最大值。

　　注意不要有区间重叠（要不就麻烦了），长度也可以优化（ i +（ 1 << j ）- 1 <= n)，-1排去第i个点的长度，因为dp[i][j-1]并不包括第i+2^j-1的那个点。

　　直接上代码：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define maxn 50005
int dp[maxn][21],dj[maxn][21];
int n,q,a[maxn],b[maxn];
void Deal_now()
{for(int i=1;i<=n;i++){dp[i][0]=a[i];dj[i][0]=a[i];}for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++){dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);dj[i][j]=min(dj[i][j-1],dj[i+(1<<(j-1))][j-1]);}    for(int i=1;i<=n;i++)b[i]=log2(i);
}
int query(int L,int R)
{int k=b[R-L+1];int ans1=max(dp[L][k],dp[R-(1<<k)+1][k]);int ans2=min(dj[L][k],dj[R-(1<<k)+1][k]);return ans1-ans2;
}
int main()
{scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%d",&a[i]);Deal_now();for(int i=1;i<=q;i++){int x,y;scanf("%d%d",&x,&y);printf("%d\n",query(x,y)); }return 0;
}