学线段树的时候学的扫描线(虽然早就看过了,一直没敲过,还是懒),现在来补一道题:
因为题目给的矩形的坐标是浮点型的,所以毫无疑问要离散化,我们以y轴坐标来建立线段树(当然也可以以x轴,这样的话扫描线是上下方向的了),然后Line表示扫描线的下一个位置。求面积的就是ans+=(line[i].x-line[i-1].x)*tree[1].cnt。其实说白了扫描线就是一个区间操作的线段树:不过节点存的是c(这个整个的区间被覆盖的次数,如果为0,则:这个整区间未被完全覆盖),cnt是整个区间所覆盖的长度。每次只需要更新这两个值就好了,设矩形的左边的权值是1,右边的权值是-1,每一条边覆盖是,总是带着权值覆盖的。因为题目