题意:

方法:线段树

解析:

题意即题解。

多次询问区间最大值与最小值的差。显然直接上线段树或者rmq维护区间最值就可以。

代码:

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 50010#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define pa pair
          
           using namespace std;int n,q;int ma[N<<2],mi[N<<2],dis[N<<2];void init(){    memset(ma,-1,sizeof(ma));    memset(mi,0x3f,sizeof(mi));}void pushup(int rt){    ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);}void build(int l,int r,int rt){    if(l==r)    {        int x;        scanf("%d",&x);        ma[rt]=mi[rt]=x;        return;    }    int mid=(l+r)>>1;    build(lson),build(rson);    pushup(rt);}pa query(int L,int R,int l,int r,int rt){    pa ret;    ret.first=-1,ret.second=0x3f3f3f3f;    if(L<=l&&r<=R)    {        pa p;        p.first=ma[rt],p.second=mi[rt];        return p;    }    int mid=(l+r)>>1;    if(L<=mid)    {        pa tmp=query(L,R,lson);        ret.first=max(ret.first,tmp.first),ret.second=min(ret.second,tmp.second);    }    if(R>mid)    {        pa tmp=query(L,R,rson);        ret.first=max(ret.first,tmp.first),ret.second=min(ret.second,tmp.second);    }    return ret;}int main(){    init();    scanf("%d%d",&n,&q);    build(1,n,1);    for(int i=1;i<=q;i++)    {        int x,y;        scanf("%d%d",&x,&y);        pa tmp=query(x,y,1,n,1);        printf("%d\n",tmp.first-tmp.second);    }}