zcmimi's blog

arrow_back扫描线共3篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一个矩形要想被保护的话,必须满足所有行 / 所有列上均有一个车的限制。这样我们解决问题就可以转化为判断一个矩形所有行上是否都有一个车了(对于列只需要把图转一下做就可以)。这样我们自然想到线段树 + 扫描线,我是用列上的扫描线从上到下,每一次扫到一个矩形的下边界就判断一下。线段树上维护每一列上距离最远的一个车的纵坐标,我们判断一个矩形是否被保护就只需要判断最远的车是否在当前矩形的范围内了。感觉OFN说的扫描线就是把问题转化到一个前缀的维护上面去其实是挺有道理的恩~

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

图形可以分割成一个个小矩阵

于是我们可以把每个矩形变成两条线段后对这些线段进行排序

如此

那么总共覆盖了多少长度?

线段树求!

那管儿子节点的事干嘛,让他们自生自灭得了

于是,我们想到,除左右端点l,r之外,在线段树的每个节点上维护两个值:该节点代表的区间被矩形覆盖的长度len,该节点自身被覆盖的次数cnt。最初,二者均为0.

注意: 每个节点代表的范围是[l,r+1],最后面的那个节点不算入统计

对于每一个(x,y1,y2,k),我们再[val(y1),val(y2)-1](离散化后的区间)上执行期间修改。该区间被线段树划分成 \log n个节点,我们把这些节点的cnt都加k

对于线段树中任意一个节点 [l,r] ,若cnt>0,则len等于raw(r+1)-raw(l)(离散化前的距离),否则,该店len等于两个子节点的len之和。在一个节点的cnt被修改,以及线段树从下往上传递信息时,我们都按照该方法更新len值。根节点的len值就是整个扫描线上被覆盖的长度

1/1
Search
search