题解：P11691 [Ynoi Hard Round 2025] 《十字神名的预言者》慈悲（色彩）

hhoppitree · 2025-02-09 12:24:06 · 题解

考虑求补集的并集的补集，也就是，离线扫描线，一开始每个点有一个颜色，每次修改将半平面的补的颜色改为 i，查询颜色为 [0,l) 的集合的点的信息和。

如果数据随机，可以考虑建立一棵 Leafy 的二叉 KD-Tree，则每次相当于将 \mathcal{O}(\log n) 个区间重染色，我们暴力递归将这棵子树划分成若干棵小子树，其中每个子树内的点颜色相同，这样修改量的总和是 \mathcal{O}(m\log n) 的，而前缀信息和询问量是 \mathcal{O}(q) 的，分块即可。

如果不随机，考虑用平面上的 Optimal Partition Tree，每次在分裂和合并的时候上传标记即可，由于上文提到的“递归处理”方式所以一个点上和子树内不可能同时有标记，这样修改的次数是 \mathcal{O}(n+m\sqrt{n}) 的，总操作次数为 \mathcal{O}(n+m\sqrt{n}+q\sqrt{m})，时间复杂度容易做到 \tilde{\mathcal{O}}(n+m\sqrt{n}+q\sqrt{m})。