矩形面积并
hdu1542
Atlantis
题意:矩形面积并思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用cnt表示该区间下边比上边多几个,sum代表该区间内被覆盖的线段的长度总和这里线段树的一个结点并非是线段的一个端点,而是该端点和下一个端点间的线段,所以题目中r+1,r-1的地方可以自己好好的琢磨一下
线段树操作:update:区间增减 query:直接取根节点的值
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
......
阅读全文