粉兔线段树

泛化

省流：通过特殊的信息维护以及 Pushup 方式维护前缀最大值的一种数据结构。

因为主要思想还是要在题里面体现所以泛化没有什么东西。

目前已知最早出现：从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法。

例题

楼房重建

Source

首先我们可以把高度的比较转化为对斜率的比较。

那么问题就转化为了求斜率的前缀最大值个数，并且支持单点修改。

这个东西是不满足幺半群性质的，没法使用线段树或者是 FhqTreap 这样的数据结构维护。

但是类似于区间最大子段和，我们可以通过修改维护的信息，更新的方式来达到维护的目的。

我们考虑维护区间最大值 \(mx\)，区间前缀最大值个数 \(cnt\)。

那么考虑合并信息，首先 \(mx\) 是特别好维护的，直接合并就行。

然后 \(cnt\) 这个玩意儿直接合并显然有问题，对于前半部分（左子树的贡献），直接拿上来是没有问题的。

但是右子树，在加入了左子树之后，\(cnt\) 的值可能有所变化，我们考虑如何处理这个贡献。

不妨设一个函数 \(calc(i, pre)\) 表示考虑维护 \(i\) 子树的答案加上 \(pre\) 这个值作为前缀最大值的影响后的答案。

首先如果在叶子节点，如果叶子节点的值大于 \(pre\)，显然就没有任何影响。

然后考虑 \(pre\) 和 \(mx(ls(i))\) 的关系。

如果 \(pre < mx(ls(i))\)，显然这个值对后面右子树没有影响（此时 \(i\) 的答案是完备的，我们是在递归更新，所以右子树的部分就不用管了），先递归进左子树把答案更新完，右子树对新答案的贡献就是原来整个子树的答案减去左子树原来的答案。

注意这个地方不能直接用右子树原来的答案，原因刚才我们说了，因为 \(cnt(i) \not= cnt(ls(i))+cnt(rs(i))\)。

否则的话左子树显然就没有贡献，右子树就直接递归进去就行了。

代码差不多长这样：

int calc(int p, int pre) {
    if(t[p].l == t[p].r) 
        return t[p].mx > pre;   
    if(pre < t[t[p].ls].mx) 
        return calc(t[p].ls, pre) + (t[p].cnt - t[t[p].ls].cnt);
    return calc(t[p].rs, pre);
}

然后每次区间修改直接令 \(cnt(i) = cnt(ls) + calc(rs, mx(ls))\) 就行。

询问直接调用 \(calc\)，于是你就能做这个题了，不过注意到我们计算右子树贡献的时候做了减法，这要求信息满足一定的区间可减性。

不妨考虑怎么去掉这个限制，我们可以令 \(cnt(i)\) 的意义改变一下，如果 \(i\) 维护了 \([l, r]\) 的信息，那么 \(cnt(i)\) 仅记录 \([mid + 1, r]\) 的信息。

但是 \(calc()\) 的含义不变，尝试写出新的 \(calc()\):

int calc(int p, int pre) {
    if(t[p].l == t[p].r) 
        return t[p].mx > pre;   
    if(pre < t[t[p].ls].mx) 
        return calc(t[p].ls, pre) + t[t[p].rs].cnt;
    return calc(t[p].rs, pre);
}

然后单点修改的时候，\(cnt(i) = calc(rs, mx(ls))\) 就行，因为我们只记录右半边的答案。

区间修改的话等下来写。

---

最后更新: September 27, 2023