P7723 [Ynoi2007] TB5x

gxy001 · 2021-10-13 10:54:06 · 题解

考虑这样一个问题，给出平面上 n 个点，m 条线，每条线把平面分成两部分，我们可以判定一个点在线的哪一侧，然后我们要按顺序对每根线的某一侧进行修改查询，操作离线，也就是说，我们要建立一种数据结构可以定位每根线的某一侧。

我们称 f(m) 为 m 条线把平面分成多少部分，那么，每个部分形成一个等价类，即进行相同的修改，我们对每个等价类建立一个节点，儿子是等价类内的所有点，维护的信息即合并子节点信息。

考虑减小问题规模，我们进行分治，把线按照操作时间分为两部分，先处理较早的操作，这部分只有 f(\frac m2) 个等价类，每个等价类都是上一层若干个的并，那么我们对每个新等价类建立一个节点，儿子是这些上一层的等价类，维护的信息即子节点信息的合并。

我们分治到 m=1 的时候，这样就得到了我们要进行修改或查询的等价类，修改直接打 tag，回溯到上一层时下放标记，这样做的复杂度为 T(m)=2T(\frac m2)+O(\min(f(m),n))。

对于这道题，由于为直线 f(m)=m^2，所以 T(m)=2T(\frac m2)+O(\min(m^2,n))。

这里似乎直接分治所有询问复杂度就是对的？但好像不好写的样子。我们考虑一种实现方式，把询问按照 B=\sqrt n 分组，每一组进行一次分治，这样复杂度就是 O(m\sqrt n)，也更好实现。

对于这道题，还有一个实现上的难点，就是交换操作导致我们无法分治时自上而下构建出这个数据结构。我们从分治的叶子节点开始构造这个数据结构，也就是从这个数据结构的根开始构建，注意到两维对称，这里只讲解一维时的情况。

进行完叶子节点的交换操作后的一维是一个由三个连续段构成的排列，一个节点的排列就是两个子节点的复合，段数为 a 和 b 的复合最多 a+b 段，所以复杂度是对的，然后一个段就是一个等价类，这里左儿子的段向父亲的段的连边是值对应相连，右儿子的段向父亲的段的连边是位置对应相连。

这样我们就建立出了这个数据结构，这道题就做完了，时间复杂度 O(m\sqrt n)。