date: 2020-09-20 12:00~17:00

2020中国大学生程序设计竞赛（CCPC） - 网络选拔赛

题目大意：有 $n$ 次操作，每次操作往平面上加个矩形，其中矩形底边在 $x$ 轴上，每次操作后求矩形并的周长。

题解：如果你把题意从周长读成了面积 : ) 那么就会发现是裸吉如一线段树。然而事实上周长仍然可以用吉如一线段树维护。

注意到周长可分成横向和纵向两个部分。对于横向部分，答案即为 $x$ 轴有矩形覆盖的长度乘 $2$。这部分容易离散化后用并查集维护。

对于纵向部分，容易发现答案为 $\sum_{i=-\infty}^{+\infty}|a_{i}-a_{i-1}|$，其中 $a_{i}$ 表示 $i$ 位置的最大值。我们可以在线段树上维护一个区间内的答案，以及左、右端点的长度，这样这棵线段树就已经是可合并的了。

考虑使用吉如一线段树维护修改。我们还需要维护最小值，最小值数量，严格次小值。考虑一次小于严格次小值的修改，那么相当于每个最小值都往上抬了一些，这会导致周长减小。

嗯？好像有些不对。只有旁边是非最小值的最小值，才会导致答案减小。因此事实上我们需要维护的不是最小值的数量，而是最小值的段数。注意这也是很容易合并的，我们判断一下左子树的 $r$ 和右子树的 $l$ 是否同时等于最小值即可。此外还有一种情况，最左边和最右边的最小值段抬高时，只会导致周长减小一倍而不是两倍（可以画图理解一下），需要特殊处理。

时间复杂度 $\mathcal{O}(n\log n)$。