自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:50:48，当前版本为作者最后更新于2017-02-26 23:12:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 40分做法-对于1，2，3，6个点

模拟

• 40分做法-对于前4个点

我们发现，高度10e9是纸老虎。完全可以离散化处理一遍。

然后我们可以很容易的得到，从0到$max(Ai,Bi,Ci)$，当然是离散化后的，之间的每个高度在初始情况下有几个露出部分。方法是从低往高扫描每一个高度，如果有一些巨石的高度低于扫描线，那么看它两边的巨石高度。如果两边都比这块高，那么加1。如果都比这个低，那么减1。

• 100分做法

其实上面的做法是预处理。假设下面的情况：

0
1        x     
1        x    x
1   x    x    x
1   x    x    x
1   x    x    x
    3    5    4

变成

0
0(-1)              
1              x
2(+1)x         x
2(+1)x         x
1    x    x    x
     3    1    4

看到了吗，当下降时，在某个高度下，这个巨石左右两边如果是空的，那么各-1，而这个高度下这个巨石两边都有巨石，那么各+1。

所以我们维护这个区间加法。

还需要继续说下去吗？线段树树状数组平衡树(treap)随便上吧。