提交记录

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num,id[50010];
long long h[50010],sum_max[50010],sum_min[50010];
void neww()
{
	num=sqrt(n);
	num=max(1,num);
	for (int i=1;i<=n;i++) id[i]=(i-1)/num+1; 
	for (int i=1;i<=id[n];i++)
	{
		long long maxx=LLONG_MIN,minn=LLONG_MAX;
		for (int j=(id[i]-1)*num+1;j<=min(n,id[i]*num);j++)
		{
			if (maxx<h[j]) maxx=h[j];
			if (minn>h[j]) minn=h[j];
		}
		sum_max[i]=maxx;
		sum_min[i]=minn;
	}
}
void qry(int l,int r)
{
	long long minn=LLONG_MAX,maxx=LLONG_MIN;
	for (int i=l;i<=min(r,id[l]*num);i++)
	{
		if (maxx<h[i]) maxx=h[i];
		if (minn>h[i]) minn=h[i];
	}
	if (id[l]!=id[r])
		for (int i=(id[r]-1)*num+1;i<=r;i++)
		{
			if (maxx<h[i]) maxx=h[i];
			if (minn>h[i]) minn=h[i];
		}
	for (int i=id[l]+1;i<id[r];i++)
	{
		if (maxx<sum_max[i]) maxx=sum_max[i];
		if (minn>sum_min[i]) minn=sum_min[i];
	}
	cout<<maxx-minn<<endl;
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>h[i];
	neww();
	for (int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		qry(l,r);
	}
	return 0;
}