题解

st表啊

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,q,xst[20][N],ist[20][N];
int pow2(int x){return (1<<x);}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&xst[0][i]);
		ist[0][i]=xst[0][i];
	}
	for(int i=1; pow2(i)-1 <=n;++i)
	{
		for(int j=1; j+pow2(i)-1 <=n;++j)
		{
			xst[i][j]=max(xst[i-1][j],xst[i-1][j+pow2(i-1)]);
			ist[i][j]=min(ist[i-1][j],ist[i-1][j+pow2(i-1)]);
			//注意这里j+pow(2,i-1)
		}
	}
	while(q--)
	{
		int l,r,g,mx,mi;
		scanf("%d%d",&l,&r);
		
		g=log2(r-l+1);
		mx=max(xst[g][l],xst[g][r-(1<<g)+1]);
		mi=min(ist[g][l],ist[g][r-(1<<g)+1]);
		printf("%d\n",mx-mi);
	}
	return 0;
}