自动搬运

查看原文

来自洛谷，原作者为

	happy_zero 坐标 FJ || 初二菜鸡

搬运于2025-08-24 22:16:14，当前版本为作者最后更新于2025-02-10 17:56:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

线段树部分参考：「题解」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$ 的个数降到了 $O(n)$ 级别，接着考虑当 $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。