题解

思路

固定两天 $x,y$ 不下雨后，一座城市会变干，当且仅当原来覆盖它的所有降雨日都属于集合 $\{x,y\}$。因此城市只需按原覆盖次数分为四类：

• 覆盖次数为 $0$：无论选择哪两天，它都已经干燥；
• 覆盖次数为 $1$：删除唯一覆盖它的那一天即可获得它；
• 覆盖次数为 $2$：必须恰好删除覆盖它的那一对天；
• 覆盖次数大于 $2$：只删除两天不可能使它干燥。

记初始干燥城市数为 $base$；one[i] 表示只被第 $i$ 天覆盖的城市数；two[i,j] 表示恰好只被第 $i,j$ 两天覆盖的城市数。选择两天 $i<j$ 后的答案就是

做法

用扫描线维护当前城市被哪些降雨区间覆盖。区间 $[l_i,r_i]$ 在 $l_i$ 加入活动集合，在 $r_i+1$ 删除。扫描每座城市时，只在活动集合大小为 $0,1,2$ 时更新上述三类统计。

对于子任务 1，可以枚举删除的两天，再重新用差分数组计算覆盖，直接得到答案。

对于子任务 2，先完成扫描线统计，再枚举全部 $\binom m2$ 对降雨日并套用公式。

完整数据中，先取 one 最大的两个值，它们给出所有没有额外 two 收益的天对中的最优值。然后只枚举实际出现在 two 映射中的天对，尝试用其额外收益更新答案。扫描线上活动集合每次变化只来自区间端点，而被记录的双覆盖对数量不超过扫描过的城市数，所以总规模是线性的。

正确性证明

首先，覆盖次数为零的城市一定始终干燥，贡献固定为 $base$。覆盖次数大于二的城市在删去任意两天后仍至少被一天覆盖，永远没有贡献。

若城市只被第 $i$ 天覆盖，它在所选两天包含 $i$ 时且仅在此时变干，所以选择 $i,j$ 时所有这类城市贡献 $one_i+one_j$。若城市恰被第 $i,j$ 两天覆盖，它只有在同时选择这两天时才变干，所以额外贡献 $two_{i,j}$。这四类互不相交且覆盖所有城市，因此固定 $i,j$ 时公式准确。

对于没有记录在 two 中的天对，额外项为零，最大的 $one_i+one_j$ 必然由 one 最大的两个不同下标取得。对于有额外项的天对，算法逐一检查。因此算法考察了每一对天可能达到的值，并取最大值，所得结果即为最优答案。

复杂度

设单组测试中城市数为 $n$、降雨日数为 $m$。

• 完整重算枚举的时间复杂度为 $O(m^2(n+m))$，空间复杂度为 $O(n)$。
• 扫描后枚举全部天对的时间复杂度为 $O((n+m)\log m+m^2)$，空间复杂度为 $O(n+m)$。
• 满分算法的时间复杂度为 $O((n+m)\log m)$，空间复杂度为 $O(n+m)$。