稍微优化的朴素算法，从O(n)到O(n^(1/2)),题目的n=50000,那么最坏情况225*200000,4千w

恩，一个点最坏在0.4秒以内，线上跑了近2秒，还行，还算是轻松的解决。

#define M 200
int i,j,k,n,T,a[505],b[505],c,d,s[50050];
main(){
	memset(a,1,sizeof(a));

	for(scanf("%d%d",&n,&T);i<n;i++){
		scanf("%d",s+i);
		if(s[i]<a[i/M])a[i/M]=s[i];
		if(b[i/M]<s[i])b[i/M]=s[i];
	}

	for(;T--;){
		scanf("%d%d",&i,&j);
		c=1e8;d=0;
		i--;j--;
		for(k=i/M+1;k<j/M;k++){
			if(a[k]<c)c=a[k];
			if(d<b[k])d=b[k];
		}
		for(k=i;k<=j&&(k%M||k==i);k++){
			if(s[k]<c)c=s[k];
			if(d<s[k])d=s[k];
		}
		for(k=j;i<=k&&(k%M!=M-1||k==j);k--){
			if(s[k]<c)c=s[k];
			if(d<s[k])d=s[k];
		}
		printf("%d\n",d-c);
	}
}