POJ-3264

这是rmq
半懂不懂（因为已经会线段树了）
但是！它的代码真的好短啊啊啊啊啊！

#include <bits/stdc++.h>
using namespace std;
int dp1[500010][20],dp2[500010][20],w[1000010];
int main(){
	int n,k,q,l,r;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>w[i],dp1[i][0]=w[i],dp2[i][0]=w[i];
	for(int j=1;1<<j<=n;j++)for(int i=1;i+1<<j-1<=n;i++)dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<j)-1][j-1]),dp2[i][j]=max(dp2[i][j-1],dp2[i+(1<<j)-1][j-1]);
	for(int i=1;i<=q;i++)cin>>l>>r,k=log2(r-l+1),cout<<max(dp2[l][k],dp2[r-(1<<k)+1][k])-min(dp1[l][k],dp1[r-(1<<k)+1][k])<<endl;
	
}