《模拟降水》题目分析
本题是一道非常难的模拟题。它改编自网上流传的一道著名的Airbnb的面试题。
首先我们大致分析一下，降水过程中水平面是怎么变化的。
第一，任何时刻，最多有2个"区间"的水平面在匀速上升，但是这两个区间上升的速率可能不同。这里"区间"指的的是若干个连续"区域"(区域是题目中的定义)组成的范围。我们称这样的区间是"激活区间"。
第二，当某个激活区间区间的水位上升到极限之后，可能会发生如下2种情况：
1) 激活区间扩展，也就是与相邻的区间合并，组成一个更大的水平面一致上升的区间。
2) 激活区间转移，也就是当前区间水平面不再上升，而另一个区间会平面开始上升。
我们以下图为例：
*
* *
** *
** ** * *
*********
123456789
假设在5号区域降水，一开始激活区间是[3, 3]和[6, 6]。
随着[3, 3]和[6, 6]水位上升到极限，激活区间变成[3, 4]和[8, 8]:
*
* *
** *
**W**W* *
*********
123456789
其中[3, 3] -> [3, 4]就是激活区间的扩展，[6, 6] -> [8, 8]就是激活区间的转移。
所以我们可以将整个降水过程划分成若干个阶段，每个阶段内激活区间不发生变化，只有激活区间的水位上升。
而一旦发生激活区间变化，就是另一个阶段的开始。
我们可以把所有N个区域划分成若干个区间，其中有(不超过)2个是激活区间。我们维护每个区间的范围以及当前的水位、极限的水位。
这样每一个阶段内的变化是容易计算的，只要我们知道这个阶段的激活区间是哪里，就能算出何时水位达到极限。
于是本题的难点就在于，当一个激活区间水位上升到极限时，如何计算下一个激活区间的范围。
这里需要根据2之前提到的2种不同的情况分别处理，其中第一种情况涉及区间的合并。
