[洛谷]P2880 [USACO07JAN] Balanced Lineup G（线段树）

ACcode:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
typedef long long ll;
ll w[N];
int n,m;
struct node{
    int l,r;
    int maxv,minv;
}tr[N*4];
void pushup(int u){
    tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
    tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
}
 
void build(int u,int l,int r){
    if(l==r)tr[u]={l,r,w[l],w[l]};
    else{
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
int query1(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r)return tr[u].maxv;
    int mid=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=mid)sum=query1(u<<1,l,r);
    if(mid<r)sum=max(sum,query1(u<<1|1,l,r));
    pushup(u);
    return sum;
}
int query2(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r)return tr[u].minv;
    int mid=tr[u].l+tr[u].r>>1;
    int sum=2e9;
    if(l<=mid)sum=query2(u<<1,l,r);
    if(mid<r)sum=min(sum,query2(u<<1|1,l,r));
    pushup(u);
    return sum;
}
int main(){
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    build(1,1,n);
    while(m--){
        int x,y;
        cin>>x>>y;
        cout<<query1(1,x,y)-query2(1,x,y)<<"\n";
    }
}

over~