题解：P5987 [PA 2019] Terytoria

· · 题解

线段树部分参考：「题解」PA2019 Terytoria。

首先需要发现，横纵坐标互不干扰，最终的答案其实就是横坐标的答案乘纵坐标的答案。

以横坐标为例。问题转化成了对于每个 (x_0,x_1) 选择覆盖 S=[x_0,x_1) 或 T=[1,x_0)\cup(x_1,n]。

但其实如果直接做考虑每个选择哪一个是很困难的，观察到两种情况区间是不交的，于是有两种办法：

扫描线+线段树

发现若已经确定了 a 在最终答案中，是可以直接推出每组 (x_0,x_1) 到底覆盖什么的。

当然不能直接枚举 x，首先要把 x 的个数降下来：将所有 x_{0/1} 离散化成 x'，则 (x'_{i-1},x'_i] 内的所有 x 是等价的，因为并没有端点在这个区间内，相当于是处在一个“空隙”中。

- 当 $x=1$ 时，所有点覆盖的都是 $T$。 - 当 $x\to x+1$ 时： - 此时 $x_0=x$ 的点原先取 $S$ 已经无法覆盖 $x+1$ 了，于是变成覆盖 $T$。 - 此时 $x_1=x$ 的点原先取 $T$ 也已经无法覆盖 $x+1$ 了，变成覆盖 $S$。 - 由于 $S,T$ 中一共就三“段”， $S\Leftrightarrow T$ 最多只会进行 2 次，因此只有上面两种情况。 按上面的步骤，复杂度均摊仍是线性的。同时，我们需要一个数据结构（最简单的是线段树）来维护被覆盖个数最多的点的覆盖个数及数量，对应区间加、全局 $\max$ 即 $\max$ 个数。 复杂度 $O(n\log n)$，但常数很大，注意 - 线段树用节点 $l$ 代表 $hsh_l-hsh_{l-1}$，这样可以只离散化 $x_0,x_1$。 - 若同时进行多次区间加，则可以将其合并一些，比如 $[1,a],(b,n]$ 加 $-1$、$(a,b]$ 加 $1$ 可合并为全局加 $1$、$(a,b]$ 加 $2$，常数可减小一半。 --- #### 哈希 当确定了所有区间覆盖 $S$ 还是 $T$ 时是容易的，我们不可能暴力枚举，但可以将 $S$ 和 $T$ 放到一起做。 难点在于保证 $S$ 和 $T$ 不能同时取。由于其是不交的，运用哈希的套路，为每一个 $S$ 和 $T$ 都随机一个权值，若选了 $A$，则将 $A$ 中的所有点的 $w$ 异或上 $A$ 的权值。 定义一种覆盖方案的 $W$ 为所有点的 $w$ 的异或和，大概率下，不同的方案下对应的是不同的 $W$，且由 $S\cup T=U$ 可以知道，每个点都被 $n$ 个区间覆盖，那么每一种 $W$ 下对应的都是一种合法的方案。 于是直接统计出 $W$ 的最大出现次数即是答案。 事实证明，哈希不一定要写异或哈希，和哈希等其实也是可以的。注意，若写异或哈希，生成的随机数得是 64 位的，否则出错概率会比较大，会 WA on #1。 --- [code](https://note.ms/731925P5987)。