线段树区间再求解

常规的线段树 push up 基本上是很方便的，至少，不用动脑子。但是有时候 push up 会很困难……因为有些信息似乎只能 $O(n)$ 维护。

这个时候，我们充分发扬人类智慧，在向上 push up 的过程中，向下通过已经求解问题的答案，得到需要的信息。若这个向下的过程每次只会涉及一个区间（类似线段树二分），复杂度就是 $O(\log n)$ 的，那么，单点修改的复杂度就是 $O(\log ^2 n)$ 的。

例1. 楼房重建

简要题意：单点修改，求大于等于前面所有数的元素个数（前缀 max 个数）。

单点修改这个东西通常都是线段树维护的。我们把问题放到线段树上。

那么，线段树每个节点需要维护的信息肯定有”前缀 max 个数“ $c$。

Push up 过程中，设左儿子答案为 $c_l$ 右儿子为 $c_r$。注意到，如果左儿子中的最大值大于等于右儿子中的最大值，那么右儿子不造成贡献，不妨维护一个“区间最大值” $g$。若 $g_l\geq g_r$，则 $c=c_l$。

若 $g_l<g_r$ 呢？那么右儿子能造成贡献。但是可以造成多少贡献呢？很难知道。一个很朴素的做法是，暴力在右儿子区间遍历。但这样复杂度爆炸了。

但我们确实需要 $O(n)$ 的信息来求解这个问题。怎么获取这么多的信息呢？我们在下层，已经加工过的信息还没有利用起来！我们在之前就已经知道每个子区间的最大值，用这个便可以二分出右边的贡献了（类似线段树上二分）。

具体地，设右儿子的左儿子 max 为 $g_{r,l}$，右儿子为 $g_{r,r}$。若 $g_l\geq g_{r,l}$，那么左儿子区间不造成贡献，直接递归右儿子继续查找。若 $g_l<g_{r,l}$，右儿子的右儿子区间，不受 $g_l$ 影响，那么造成的贡献就是受 $g_{r,l}$ 影响的答案（或者说大于 $g_{r,l}$ 的个数）：$c_r-c_{r,l}$。不能是 $c_{r,r}$，因为我们要考虑受 $g_{r,l}$ 的影响。左儿子造成的影响可以递归求解。每次只往一个区间查找，复杂度就是 $O(\log n)$ 的。

这样整个问题就被 $O(q\log^2 n)$ 解决了。

还有另一种写法，不需要减法。减法是在求右儿子的时候有的，那么将 $c$ 维护的东西改为“右儿子的前缀 max 个数”，就可以只有加法了。缺点是，询问的复杂度从 $O(1)$ 变为 $O(\log n)$。

例2. 栈的维护

神奇吧，一本通有这种题。

还是用线段树维护，类似的思路。

每个节点维护“区间元素和”$s$，“区间元素个数”$c$，和”区间向前影响（弹出）个数“$d$。

若 $c_l\leq d_r$，那么左儿子区间会被清空，即 $c\gets c_r,s\gets s_r,d\gets d_l+d_r-c_l$。

反之，左儿子区间不被清空，需要求，左儿子被删除 $d_r$ 个之后的区间元素和。

递归过程中，若 $c_r\leq d$，右儿子被清空，那么，$d\gets d-c_r+d_r$（$+d_r$ 是因为要考虑右边区间对左边的影响），往左儿子递归求解。否则，左儿子没有被多余的删除，只用考虑 $d_r$，所以贡献是 $s-s_r$（类似上一题所说的），然后递归往右儿子求就好了。

总复杂度也是 $O(q\log^2 n)$。