线段树求调

#include<bits/stdc++.h>
using namespace std;
#define lson (i<<1)
#define rson (i<<1|1)
const int INF = 0x3f3f3f3f; 
const int N = 5e4 + 5;
struct node{
	int l,r,max,min;
}a[N * 4];
int n,q,h[N];

void build(int i,int l,int r)
{
	a[i].l=l;
	a[i].r=r; 
	if(l==r){
		a[i].min=h[l];
		a[i].max=h[l];
		return ;
	}
	int mid = (l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	a[i].max=max(a[lson].max,a[rson].max);
	a[i].min=min(a[lson].min,a[rson].min);
}

int query(int i,int l,int r)
{
	if(a[i].l>=l&&a[i].r<=r) return a[i].max;
	int ma=0;
	if(a[lson].r>=l) ma=max(ma,query(lson,l,r));
	if(a[rson].l<=r) ma=max(ma,query(rson,l,r));
	return ma;
}

int query2(int i,int l,int r)
{
	if(a[i].l>=l&&a[i].r<=r) return a[i].min;
	int mi=INF;
	if(a[lson].r>=l) mi=min(mi,query(lson,l,r));
	if(a[rson].l<=r) mi=min(mi,query(rson,l,r));
	return mi;
}
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
	}
	build(1,1,n);
	for(int i=1;i<=q;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%d\n",query(1,x,y)-query2(1,x,y));
	}
	return 0;
}