题意：n个数字，q个询问，问第A个到第B个数的极差。
思路：线段树，每个节点记录节点包括范围的最大值和最小值。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int l,r;
int ma,mi;
}t[50005*4];
int n,q,a[50005],s,e;
int mma,mmi;
void create(int ll,int rr,int rot)
{
t[rot].l=ll;
t[rot].r=rr;
if(ll==rr)
{
t[rot].ma=a[ll];
t[rot].mi=a[ll];
}
else
{
int mid=(ll+rr)/2;
create(ll,mid,rot<<1);
create(mid+1,rr,rot<<1|1);
t[rot].ma=max(t[rot<<1].ma,t[rot<<1|1].ma);
t[rot].mi=min(t[rot<<1].mi,t[rot<<1|1].mi);
}
}
void query(int ll,int rr,int rot)
{
if(t[rot].l==ll&&t[rot].r==rr)
{
mma=max(mma,t[rot].ma);
mmi=min(mmi,t[rot].mi);
}
else
{
int mid=(t[rot].l+t[rot].r)/2;
if(rr<=mid)
{
query(ll,rr,rot<<1);
}
else if(ll>mid)
{
query(ll,rr,rot<<1|1);
}
else
{
query(ll,mid,rot<<1);
query(mid+1,rr,rot<<1|1);
}
}
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
create(1,n,1);
for(int i=0;i<q;i++)
{
scanf("%d%d",&s,&e);
mma=0;
mmi=1000001;
query(s,e,1);
cout<<mma-mmi<<endl;
}
return 0;
}