这里用HDU的1542题作为例子，一个经典的扫描线题目，计算矩形并的和。

　　首先介绍扫描线，就是一根假想的线，从左到右的一条竖线扫描过去。

　　扫描线可以用来填充多边形，具体请看   写的很好。

　　然后就是扫描线在这个题里的应用。

　　

　　计算这两个矩形的面积等价于计算红色，绿色，蓝色三块的面积的和。

　　所以说从左到右的扫描线扫描的时候，线段树维护的是区间内被覆盖的总长度，然后乘以两条扫描线之间的距离，就是一块的面积，然后更新线段树，以此论推，得到的就是总面积了。

　　不过这个题要注意三个地方：

　　1，离散化，每条边的坐标是浮点数，要进行离散化，要记得去重。

　　2，就是区间覆盖的长度计算问题，这里我纠结了老久，首先如果按照点来覆盖的话对区间2，8覆盖其实是对1，5和6，10进行覆盖（如果线段树左右子树的区间是1，5和6，10的话，那么5和6中间那一块就没有被计算上，就出问题了。。。

　　所以说不能按照点来覆盖，应该把每个点当作是表示这个点到下一个点之间的这条线段，这样就不会漏掉中间那一个了。

　　如果是表示线段的话，那么如果有10个点，那么有9条线段，所以线段树是1到9（而不是10），每次计算长度的时候记得右边要加一。

　　3，就是线段树的更新问题，每加一条线段或者减一条线段的话，并不是简单的覆盖就好，而是应该记录这个区间被覆盖了几次，直到减到零的时候才是没有线段在覆盖这个区间。这样的话每加一条线段就是对线段的区间+1，去一条线段就是-1。

　　不过这样的话pushDown就不好用了，因为如果把一个节点的COL值推到下面两个之后，之后如果再覆盖，这个节点的COL变成-1了，那就不好算这个节点维护的值了。所以根据杭电大神的写法，不用pushDown，而是在计算pushUP的时候，如果这个节点已经被覆盖为大于0的就直接计算（因为这个节点表示的整个区间都被覆盖了，直接右面减去左面就是了。），否则才求助于下面的两个节点。而且，询问只是询问节点1的值，所以不会出错。

 

　　近来又看到了一个大神的线段树写法，他用了pushDown，但是也对pushUP进行了修改，从而保证不会让某一个节点的值为零，虽说速度不会快，但是可扩展性要高很多，因为可以让有的矩形第一条边为-1，第二条边为1（HDU  3265）这个题。

　　修改的代码我在HDU  3265和HDU  1542中都贴出来了。

 

　　差不多就这三个了，水平有限，敬请谅解。

 

例题：

　　  。

　　  。

　　  。