View Code of Problem 2897

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn=1e6+10;
const int inf=0xffffff0;
typedef long long ll;
//线段树 
struct Node{
	int l,r;
	ll maxx,minx,flag;
	Node(){
	};
	Node(int _l,int _r,ll _v1,ll _v2,ll _f){
		flag=_f,l=_l,r=_r,maxx=_v1,minx=_v2;	
	};
	int mid(){
		return (l+r)/2;
	};
	
};

Node a[maxn*4];
void build(int k,int l,int r){		//建树 
	a[k]=Node(l,r,0,0,0);
	if(a[k].l==a[k].r){
		ll t;
		scanf("%lld",&t);
		a[k].maxx=t;
		a[k].minx=t;
		return;
	}
	build(k<<1,l,(l+r)/2);
	build(k<<1|1,(l+r)/2+1,r);
	a[k].maxx = max(a[k*2].maxx,a[k*2+1].maxx);
	a[k].minx = min(a[k*2].minx,a[k*2+1].minx);
//	a[k].w=a[k<<1].w+a[k<<1|1].w;
}

//void down(int k){					//延迟标记下传 
//	a[k<<1].flag+=a[k].flag;
//	a[k<<1|1].flag+=a[k].flag;
//	a[k<<1].w+=a[k].flag*(a[k<<1].r-a[k<<1].l+1);
//	a[k<<1|1].w+=a[k].flag*(a[k<<1|1].r-a[k<<1|1].l+1);
//	a[k].flag=0;
//}
//
//ll res;

//void update(int k,int x,int y,ll z){	//区间更新 
//	if(a[k].l>=x&&a[k].r<=y){
//		a[k].w+=z*(a[k].r-a[k].l+1);
//		a[k].flag+=z;
//		return;
//	}
//	if(a[k].flag)
//		down(k);
//	if(x<=a[k].mid())
//		update(k<<1,x,y,z);
//	if(y>a[k].mid())
//		update(k<<1|1,x,y,z);
//	a[k].w=a[k<<1].w+a[k<<1|1].w;
//	
//}

ll maxx;
ll minx;
void query(int k,int x,int y){			//区间查询 
	if(a[k].l>=x&&a[k].r<=y){
		maxx = max(a[k].maxx,maxx);
		minx = min(a[k].minx,minx);
		return;
	}

//	if(a[k].flag)
//		down(k);
	if(x<=a[k].mid())
		query(k<<1,x,y);
	if(y>a[k].mid())
		query(k<<1|1,x,y);
//	a[k].w=a[k<<1].w+a[k<<1|1].w;	
}


int main()  
{  
    int n,p,h;
    int a1,a2;
    scanf("%d%d",&n,&p);
    build(1,1,n);
    for(int i=0;i<p;i++){
        scanf("%d%d",&a1,&a2);
        minx=inf;
        maxx=-inf;
        query(1,a1,a2);
        printf("%lld\n",maxx-minx);
    }
    return 0;
}