题目大意：给定每个矩形的对角线的两个端点，让你求这些矩形的面积的并集，即重叠的不能重复计算
题目分析：这题就是典型的线段树求面积并
离散化：对所有节点的Y进行升序排序，然后以Y的位置建树，就是指，在线段树里面，左右节点的实际意义就是指这个线段在Y的升序数组里的位置，但是我们把lf,rf赋值为这个线段左右端点的具体值，这就是离散化
建树的细节：树的每个节点有lf,rf,cover,lenth，分别指这个节点所表示的线段的左端点，右端点，被覆盖的次数（在这里覆盖的次数是为了区分重叠矩形的情况下，高度的正确存取，因为一个矩形对Y轴的覆盖是以他的左边开始，右边结束的，所以当插入左边的时候，我们把cover+1，右边的时候把cover-1，说明这个矩形对Y的覆盖已经结束，计算下一个矩形时，不会错误的把我这个矩形的高度当作下一个矩形的高度），lenth指这个区间被矩形覆盖的长度即矩形的实际高度；插入的时候，先把存放节点的数组，对X进行升序排序，然后顺次插入，分别计算

http://blog.csdn.net/u011328276/article/details/9496999

• Re:题解 举行面积求并 离散化 (38) a1b3c7d9 2019-08-19 17:20:23