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

· · 题解

线段树都有了，怎能少了树状数组？？

那我来补一发。

其实这道题有很多种解法，也有写ST表的，而且貌似时间复杂度还比较优秀。

但是多一种解法毕竟是好事，可以从不同角度去做一道题。

有一位巨佬也用的树状数组，但是貌似只贴了个代码，我这里还是发一下详细的题解，毕竟有些人可能不知道如何维护最大最小值。

进入正题：

既然明说了需要树状数组，那么肯定要知道树状数组是什么

不知道树状数组是什么的童鞋们戳这戳这戳这QWQ

阅读题面，很容易就可以发现题目要求区间查询最大值与最小值的差。

那么我们就用两个树状数组，分别维护所有数据的最大值和最小值。

这个就不过多赘述了，应该都懂。

int lowbit(int x)
{
    return x & -x;
}

首先从建树开始。

前面我们提到过，我们使用两个树状数组维护最大值和最小值，我们姑且把维护最大值的树状数组定义为treex，维护最小值的则定义为treen

那么，在向上传递的过程中，我们每传递一层，就比较一次，更新一次点。

这里打个比方：

就像刚刚那样，每次传递最大值与最小值（就是把求区间和树状数组中的累加改为了求最值）

建树代码：

void _add(int x, int k)//建树QAQ 
{
    for(;x <= n; x += lowbit(x))
    {
        treex[x] = max(treex[x], k);
        treen[x] = min(treen[x], k);
    }
}

我们刚刚说过，建树时可以直接套区间和的板子，只需要把累加改成求最值就可以了。

但是求最大值与最小值不行。因为他没有像求区间和那样的性质。

因为区间合中，要查询[x,y]的区间合，是求出[1,x-1]的合与[1,y]的合，然后相减就得出了[x,y]区间的合。

但是很明显，求最值是不能相减求得的，这个时候我们就要想另外一种办法。

我们这里分两中情况讨论

这两种情况想明白之后，就可以用递归解决问题了。

递归到某一层时，x == y，这个时候返回 a[x] 或 a[y] 就行了。（毕竟 x == y时，区间[x,y]就只有a[x]这一个数据了）

贴这部分的代码：

//下面两个子函数本质上是一样的

int _findmax(int x, int y)//区间查询最大值 
{ 
    if(y > x)
    {
        if(y - lowbit(y) > x) return max(treex[y], _findmax(x, y - lowbit(y)));
        else return max(a[y], _findmax(x, y - 1));//如上所述
    }
    return a[x];
}

int _findmin(int x, int y)//区间查询最小值 
{ 
    if(y > x)
    {
        if(y - lowbit(y) > x) return min(treen[y], _findmin(x, y - lowbit(y)));
        else return min(a[y], _findmin(x, y - 1));
    }
    return a[x];
}

上面这两个处理完之后，就可以合并代码了。

毕竟这里没有什么单点修改之类的操作。

这里有一个要注意的点：treen（维护最小值的树状数组）最开始要全部赋值为inf。毕竟是存最小值。而treex（维护最大值的树状数组）就不管了，因为没有数据小于0。（实际上建树的表格里就体现出这一点了）

最后按照题目要求来，用区间最大值减去最小值就可以了。

上代码！

#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
using namespace std;

int n, m;
int a[50005] ,treex[50005], treen[50005];

int lowbit(int x)//求lowbit:2进制下末尾0的个数。可表示tree中包含数据数量 
{
    return x & -x;
}

void _add(int x, int k)//建树QAQ 
{
    for(;x <= n; x += lowbit(x))
    {
        treex[x] = max(treex[x], k);
        treen[x] = min(treen[x], k);
    }
}

int _findmax(int x, int y)//区间查询最大值 
{ 
    if(y > x)
    {
        if(y - lowbit(y) > x) return max(treex[y], _findmax(x, y - lowbit(y)));
        else return max(a[y], _findmax(x, y - 1));
    }
    return a[x];
}

int _findmin(int x, int y)//区间查询最小值 
{ 
    if(y > x)
    {
        if(y - lowbit(y) > x) return min(treen[y], _findmin(x, y - lowbit(y)));
        else return min(a[y], _findmin(x, y - 1));
    }
    return a[x];
}

int main()
{
    memset(treen, 0x3f3f3f3f, sizeof(treen));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) 
    {
        scanf("%d", &a[i]);
        _add(i, a[i]);
    }
    for(int i = 1; i <= m; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        cout << _findmax(l, r) - _findmin(l, r) << endl;
    }
    return 0;
}

（悄悄求赞，应该没人发现我QAQ）