henrytb 的博客

henrytb 的博客

题解 P2880 【[USACO07JAN]平衡的阵容Balanced Lineup】

posted on 2019-05-20 18:21:16 | under 题解 |

线段树大法好!

这道题一看就是一道线段树模板题,区间求最大最小

对于每个区间维护一个max值和一个min值,在线段树里的pushup函数里更新,最后相减即可QAQ

PS:线段树码风一定要很好,要不然连自己都看不懂了。。。最近改码风一下就把线段树背下来了。我是define了ls和rs表示左右儿子,又改用结构体存线段树,效果很优秀

呆码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ls(p) p*2
#define rs(p) p*2+1
using namespace std;
const int N=50005;
struct node{
    int l,r,maxx,minn;
}t[N*4];
int n,q,num[N];
void pushup(int p){
    t[p].maxx=max(t[ls(p)].maxx,t[rs(p)].maxx);
    t[p].minn=min(t[ls(p)].minn,t[rs(p)].minn);
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].maxx=num[l];t[p].minn=num[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
}
int askmax(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].maxx;
    }
    int ans=-1;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)ans=max(ans,askmax(ls(p),l,r));
    if(mid<r)ans=max(ans,askmax(rs(p),l,r));
    return ans;
}
int askmin(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].minn;
    }
    int ans=0x3f3f3f3f;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)ans=min(ans,askmin(ls(p),l,r));
    if(mid<r)ans=min(ans,askmin(rs(p),l,r));
    return ans;
}
int main(){
    scanf("%d%d",&n,&q);
    rep(i,1,n)scanf("%d",&num[i]);
    build(1,1,n);
    rep(i,1,q){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",askmax(1,l,r)-askmin(1,l,r));
    }
    return 0;
}