我是用线段树;
不知对你们可否又能用
#include<cstdio>
#include<cstdlib>
#include<algorithm>
int f[500000],max[500000],min[500000],a[200001],ft[500000];
void make(int p,int x,int y)//建树
{
if (x==y) {f[p]=0;max[p]=a[x];ft[p]=0;min[p]=a[x];return;}
int t,mid=(x+y)/2;
make(p*2,x,mid);make(p*2+1,mid+1,y);
f[p]=f[p*2]>f[p*2+1]?f[p*2]:f[p*2+1];
ft[p]=ft[p*2]>ft[p*2+1]?ft[p*2]:ft[p*2+1];
min[p]=min[p*2]<min[p*2+1]?min[p*2]:min[p*2+1];
max[p]=max[p*2]>max[p*2+1]?max[p*2]:max[p*2+1];
if (max[p*2+1]-min[p*2]>f[p])f[p]=max[p*2+1]-min[p*2];
if (max[p*2]-min[p*2+1]>ft[p])ft[p]=max[p*2]-min[p*2+1];
}
int search(int p,int L,int R,int l,int r,int &minx,int &maxx)//找min在max左侧的情况 ；
{
if(L==l&&R==r){minx=min[p];maxx=max[p];return f[p];}
int mid=(L+R)/2,maxx1,minx1,maxx2,minx2;
if (r<=mid){int t=search(p*2,L,mid,l,r,minx1,maxx1);minx=minx1;maxx=maxx1;return t;}
else if(l>mid){int t=search(p*2+1,mid+1,R,l,r,minx2,maxx2);minx=minx2;maxx=maxx2;return t;}
else {
int tot1=search(p*2,L,mid,l,mid,minx1,maxx1);
int tot2=search(p*2+1,mid+1,R,mid+1,r,minx2,maxx2);
int t=tot1>tot2?tot1:tot2;
minx=minx1<minx2?minx1:minx2;
maxx=maxx1>maxx2?maxx1:maxx2;
if (maxx2-minx1>t)t=maxx2-minx1;return t;
}
}
int search2(int p,int L,int R,int l,int r,int &minx,int &maxx)//找max在min左侧的情况；
{
if(L==l&&R==r){minx=min[p];maxx=max[p];return ft[p];}
int mid=(L+R)/2,maxx1,minx1,maxx2,minx2;
if (r<=mid){int t=search2(p*2,L,mid,l,r,minx1,maxx1);minx=minx1;maxx=maxx1;return t;}
else if(l>mid){int t=search2(p*2+1,mid+1,R,l,r,minx2,maxx2);minx=minx2;maxx=maxx2;return t;}
else {
int tot1=search2(p*2,L,mid,l,mid,minx1,maxx1);
int tot2=search2(p*2+1,mid+1,R,mid+1,r,minx2,maxx2);
int t=tot1>tot2?tot1:tot2;
minx=minx1<minx2?minx1:minx2;
maxx=maxx1>maxx2?maxx1:maxx2;
if (maxx1-minx2>t)t=maxx1-minx2;return t;
}
}
int main()
{
int n,m,x,y,minx,maxx;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
make(1,1,n);scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if(x<=y)printf("%d\n",search(1,1,n,x,y,minx,maxx));
else {std::swap(x,y);printf("%d\n",search2(1,1,n,x,y,minx,maxx));}
}
//system("pause");
return 0;
}