题解思路：线段树维护每段中的最大和最小值。
代码：
#include<algorithm> #include<cstdio> #include<cstring> #include<iostream> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 5e4+10; int n,m,MAX[mx<<2],MIN[mx<<2],num; struct data{ int maxx,minn; data(){} data(int Ma,int Mi){ maxx = Ma, minn = Mi ; } }; void build(int l,int r,int rt){ if(l==r){ scanf("%d",&num); MAX[rt] = MIN[rt] = num; return ; } int mid = (l+r)>>1; build(lson); build(rson); MAX[rt] = max(MAX[rt<<1],MAX[rt<<1|1]); MIN[rt] = min(MIN[rt<<1],MIN[rt<<1|1]); } data query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return data(MAX[rt],MIN[rt]); int mid = (l+r)>>1; data po[2]={{0,inf},{0,inf}}; if(L<=mid) po[0] = query(L,R,lson); if(R>mid) po[1] = query(L,R,rson); return data(max(po[0].maxx,po[1].maxx),min(po[0].minn,po[1].minn)); } int main(){ while(~scanf("%d%d",&n,&m)){ build(1,n,1); while(m--){ int x, y; scanf("%d%d",&x,&y); data ans = query(x,y,1,n,1); printf("%d\n",ans.maxx-ans.minn); } } return 0; }