题目描述
题解
楼房重建的提高版。
用线段树维护每个区间的单调不下降的元素个数。
我们可以考虑假设左区间和右区间的个数已经知道了，现在要合并。
所以要用左区间的最大值 $v$ 来计算右区间能加进来的个数。
于是递归右区间，如果其左区间的最大值小于 $v$ ，那就递归右区间，否则递归左区间再加上右区间的个数即可。
右区间的个数就是区间个数-左区间个数。
效率： $O(nlog^2n)$ 。
代码
题目描述
题解
楼房重建的提高版。
用线段树维护每个区间的单调不下降的元素个数。
我们可以考虑假设左区间和右区间的个数已经知道了，现在要合并。
所以要用左区间的最大值 $v$ 来计算右区间能加进来的个数。
于是递归右区间，如果其左区间的最大值小于 $v$ ，那就递归右区间，否则递归左区间再加上右区间的个数即可。
右区间的个数就是区间个数-左区间个数。
效率： $O(nlog^2n)$ 。
代码
![开源按键组件Multi_Button的使用,含测试工程[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)