Balanced Lineup（线段树）

题目传送门

Balanced Lineup

题目大意

一片绿地的N(1≤N≤50000)颗树排成一排，q次查询，每次查询区间最大值和最小值之差

思路

很ez的线段树了，更新和push_down都不需要，lazy标记也无
直接线段树维护区间最大值和最小值即可

AC Code

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int, int > PII;
#define debug(a) cout<<#a<<"="<<a<<endl;
#define INF 0x3f3f3f3f
const int N=5e4 +9;
int n, q, x, y;
int a[N];
struct segtree{
    int l, r;int minv, maxv;
}tr[N<<2];
inline int read()
{
    int ans=0;char last=' ',ch=getchar();while(ch<'0'||ch>'9') last=ch,ch=getchar();while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();if(last=='-') ans=-ans;return ans;
}
inline int lc(int p) {
    return p<<1;}
inline int rc(int p) {
    return p<<1|1;}
inline void push_up(int p){
    tr[p].maxv=max(tr[lc(p)].maxv, tr[rc(p)].maxv);tr[p].minv=min(tr[lc(p)].minv, tr[rc(p)].minv);
}
inline void build(int p, int l, int r){
    tr[p].l=l, tr[p].r=r;if(l==r)	{
    tr[p].maxv=tr[p].minv=a[l]; return ;}int mid=(l+r)>>1;build(lc(p), l, mid);build(rc(p), mid+1, r);push_up(p);
}
inline PII query(int p, int l, int r,int x, int y){
    if(x>r || y<l)	return PII(-INF, INF);if(l<=x && y<=r) return PII(tr[p].maxv, tr[p].minv);int mid=(x+y)>>1;PII ql=query(lc(p), l, r, x, mid);PII qr=query(rc(p), l, r, mid+1, y);return PII(max(ql.first, qr.first), min(ql.second, qr.second));
}
int main(){
    n=read(); q=read();for(int i=1; i<=n; i++) a[i]=read();build(1,1,n);for(int i=1; i<=q; i++){
    x=read(); y=read();PII a=query(1,x,y,1,n);cout<<a.first-a.second<<endl;}return 0;   
}