俊秀超短裙

文章
4
资源
0
加入时间
2年10月24天

矩形面积交(线段树+扫描线)

传送门我们要计算被覆盖两次或以上的部分面积,我们在线段树节点中增设了一个变量,more,其中len表示该该区间内被覆盖了1次或以上的长度,more表示被覆盖了2次或以上的长度怎么计算最后的面积的?一样的道理,从下往上扫描矩形,每次添加一条矩形上下边,然后看看t[1].more是多少,再乘上高度差。因为t[1]表示了总区间,而more表示被覆盖两次或以上的长度,即计算时我们忽略掉只被覆盖一次...