题目传送门
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;
}
