-
题目链接 题意: 求n(1000)个矩形的面积交,也就是至少有2个矩形覆盖的区域的面积。 思路: 和矩形面积并_hdu1542解题报告 类似 面积并问题中,线段树len维护的是至少覆盖一次的区域的长度 在面积交的问题中,我们需要多维护一个"至少覆盖两次的区域的长度"的域(设为double two;) 同时也要维护至少覆盖一次的区域的长度(设为double one;),是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到(好像是废话) PushUp的时候要格外注意当前节点被完整覆盖一次的情况。 此时tree[rt].two 可以由两个子区间的one的情况想加得到 (因为rt节点被完整覆盖了至少一次,那么 …
Read More