本文共 528 字，大约阅读时间需要 1 分钟。

题目大意：

有一些屋顶，相当于一些线段（不相交）。问每一条线段能够接到多少水，相对较低的屋顶能够接到高屋顶留下的水。

解题思路：

扫描线，由于对于同一个x最多有25条线段。所以不须要线段树更新。在扫描线的过程中构造出线段与线段之间的关系。好在最后计算每一个屋顶能够接多少水。

以下是代码：

[代码部分]

经过处理，点的数量为pointcnt。然后对点进行排序并去重。接着对线段进行排序。

初始化last=0, now=0, tail=0, levelcnt=0。

然后开始循环：

对于每个点i，设置now=point[i]。

如果levelcnt不为0，则将segment[a[levelcnt-1]]的w增加now-last。

然后进入一个内部循环：

当tail的x1等于now且tail的x1不为n时，进入处理。

在这一步，通过比较线段的y值，找到与now相连的线段。然后按照层级进行更新。

对于每个线段，根据它的x1和x2是否等于now，来决定下一步的操作。

最后，设置levelcnt为cnt的值。

然后使用队列进行广度优先遍历，计算每个线段的w值。

最终结果保存在ans数组中。

代码部分完成后，对每个线段的num输出ans值。

[优化后的内容]

转载地址：http://muxfk.baihongyu.com/