题解 P3616 【富金森林公园】

kkksc03 · 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)随便上吧。