难度： 黄

ST 表板子。

#include<bits/stdc++.h>
using namespace std;
struct st_tab{
	int n,a[50050][20],b[50050][20],lg[50050];
	inline int q1(int x,int y){
		if(x>y) swap(x,y);
		int p=lg[y-x],d=1<<p;
		return max(a[x][p],a[y-d+1][p]);
	}
	inline int q2(int x,int y){
		if(x>y) swap(x,y);
		int p=lg[y-x],d=1<<p;
		return min(b[x][p],b[y-d+1][p]);
	}
	inline void init(queue<int> q){
		while(!q.empty()){
			n++;
			int u=q.front();
			q.pop();
			a[n][0]=b[n][0]=u;
		}
		for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
		for(int k=2,j=1;k<=n;k*=2,j++){
			for(int i=1;i+k-1<=n;i++){
				a[i][j]=q1(i,i+k-1);
				b[i][j]=q2(i,i+k-1);
			}
		}
	}
}t;
int n,m,a,b;
queue<int> q;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		q.push(a);
	}
	t.init(q);
	while(m--){
		scanf("%d%d",&a,&b);
		printf("%d\n",t.q1(a,b)-t.q2(a,b));
	}
}