题解 P1816 【忠诚】

Inkyo · 2019-10-17 10:11:13 · 题解

题目，blog阅读体验更佳

想用树状数组其实也可以。线段树难写又难调，ST表不好维护边界条件。相对来说树状数组要均衡一些。

已经有人写了树状数组做法了（而且还在第一页，可以自己去看）。但是他并没有解释树状数组如何解决此类问题。我这里来补充一下。

建树没什么好说的，把传统树状数组的加改成求最值函数即可。

但是对于区间求最值，有人表示有些看不懂

guodong：“getmin函数有点蒙”

这里解释一下树状数组区间求最值的方法。

假设我们现在要求[x,y]的区间最值。对于求区间和的树状数组来说，我们一般是求[1,x-1]和[1,y]的区间和，然后再相减得到答案。显然求最值不满足这种性质。

我们可以考虑拆开[x,y]这个区间。以下，我们分两种情况讨论

• The first case： 当y-lowbit(y) > x时

  显然，我们可以把[x,y]拆成[x,y-lowbit(y)] 和[y-lowbit(y) + 1,y]。拆成这个样子有什么好处呢？如果再细心一点，可以发现[y-lowbit(y) + 1,y]其实就是tree[y]。 这里可以自己口算一下验证。

  这样，我们求最值的区间直接减小了一半。效率其实还不错。

• The second case： 当y-lowbit(y) < x

  这种情况下，由于y-lowbit(y)会超过左区间范围，这个时候，考虑直接把[x,y]拆为[x,y - 1] 与 a[y]。这样看似只拆了一个出来，但是拆过后[x,y - 1]区间可能就满足了第一种情况。 所以效率其实也很不错。

  然后，上述过程用递归完成即可。当递归到某一层，x==y，这个时候返回a[x]或者a[y]即可

代码大致是这样的：

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

剩下的，写个标准的树状数组即可。