QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: mxm

Posted at:

Last updated:

Back to Problem

New Editorial for Problem #10119

考虑假设我们已经知道每个砖的位置,该如何数空腔。扫描线记录每个高度每个位置有没有砖(有砖为 $1$,没砖为 $0$)。则放上一个砖后会使一个空腔封顶当且仅当一段完整的 $0$ 区间被当前砖覆盖为 $1$。而维护连续段正是 ODT 所擅长的。因此可用 ODT 实现。

具体地,分裂节点与区间修改操作与普通 ODT 相同。而统计操作则检查左右端点对应的区间(可能未被完全覆盖)及其中间的区间(一定被完全覆盖)即可。

至于如何统计砖的位置,这也是个区间覆盖问题,也能用 ODT 做,代码较短。由于每次操作后都立即进行了区间覆盖(同一层操作互不影响),时间复杂度正确。

注意细节:

  1. 同一层操作顺序一定是先统计,再删(覆盖 $0$),最后加(覆盖 $1$)。
  2. 普通 ODT 不保证相邻段不同色,需维护段使其相邻不同色。
  3. 一个空腔可能由两块砖封顶!而由于先统计,后一块砖看不到前一块砖的存在,因此需要将同层相邻同种操作合并为一个!

Comments

No comments yet.