#include <cstdio>
#include <algorithm>
using namespace std;
int q,x,y,n,a[50005],f1[150005],f2[150005];
void JZ (int i,int x,int y)
{
    if(x==y){f1[i]=a[x];f2[i]=a[x];return;}
    int m=(x+y)/2;JZ (2*i,x,m);JZ (2*i+1,m+1,y);
    f1[i]=max(f1[i*2],f1[i*2+1]);f2[i]=min(f2[i*2],f2[i*2+1]);
}
int CZ1 (int i,int x,int y,int q,int w)
{
    if(x>=q&&y<=w)return f1[i];
    int m=(x+y)/2;
    if(w<=m)return CZ1 (i*2,x,m,q,w);
     else if(q>m)return CZ1 (i*2+1,m+1,y,q,w);
      else return max(CZ1 (i*2,x,m,q,w),CZ1 (i*2+1,m+1,y,q,w));
}
int CZ2 (int i,int x,int y,int q,int w)
{
    if(x>=q&&y<=w)return f2[i];
    int m=(x+y)/2;
    if(w<=m)return CZ2 (i*2,x,m,q,w);
     else if(q>m)return CZ2 (i*2+1,m+1,y,q,w);
      else return min(CZ2 (i*2,x,m,q,w),CZ2 (i*2+1,m+1,y,q,w));
}
int main ()
{
	scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    JZ (1,1,n);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&x,&y);
        int m1=CZ1 (1,1,n,x,y);
        int m2=CZ2 (1,1,n,x,y);
        printf("%d\n",m1-m2);
    }
}

• Re:线段树也不长啊，38行，在2016年跑了2016MS，有趣！！！ (1148) piupiup 2019-08-12 10:26:10