【题解】洛谷 P7737 [NOI2021] 庆典

· · 题解

注：本题为 NOI2021 D1T3。

题解

首先，本题只考虑可达关系，因此毫不犹豫地缩点+拓扑排序。

记所得图为 G，显然 G 是一个有向无环图。

然后考虑题目条件：

  1. 将 C 国原有的有向道路视为无向道路后，所有城市可以互达。
  2. 若 x \Rightarrow z 且 y \Rightarrow z，则 x \Rightarrow y 或 y \Rightarrow x。

可知：G 中必然存在一个点，它能到达其它所有点，即 G 形成一棵外向树。

证明

取 G 中入度为 0 的任意一个点为 root。

由条件 1 知，对于不同于 root 的任意一个点 x，有以下四种情况：

  1. root \Rightarrow x
  2. x \Rightarrow root
  3. 存在点 y 满足 x \Rightarrow y 且 root \Rightarrow y。
  4. 存在点 y 满足 y \Rightarrow x 且 y \Rightarrow root。

由于 root 入度为 0，第 2,4 种情况不可能出现。

对于第 3 种情况，由条件 2 知 x \Rightarrow root 或 root \Rightarrow x。

因此一定有 root \Rightarrow x，即 root 能到达其它所有点。

（下文不再讨论原图，只讨论所得的外向树）

再考虑题目所求：额外加入 k 条有向边，问有多少个点 x，满足 s \Rightarrow x 且 x \Rightarrow t。

设 S=\{x|s\Rightarrow x\}，T=\{x|x\Rightarrow t\}，问题即求 |S \cap T|。

记 x 的子树中点组成的集合为 Sub_x，x 到根路径上点组成的集合为 R_x。

对于 k=0，有 S=Sub_s，T=R_t。

考虑新加入一条边 a \to b：

注意：由于无法确定边的顺序，需要 O(k^2) 尝试加入每条边。

那么如何记录 S,T 并求解 |S \cap T| 呢？

S 和 T 其中一个在树剖线段树上打标记，另一个用数组记录点编号，在树剖线段树上查询即可。

当然需要处理重复计算的问题，处理方式有三种：

  1. （适用于 S 在树剖线段树上打标记）处理到根路径的并集：记 T 中点按树剖序从小到大排序依次为 T_1,T_2,\cdots,T_{|T|}，则答案为 \sum_{i=1}^{|T|}R_{T_i}-\sum_{i=1}^{|T|-1}R_{\operatorname{LCA}(T_i,T_{i+1})}。
  2. （适用于 T 在树剖线段树上打标记）处理子树的并集：记 S 中点的子树的树剖序区间，按第一关键字为左端点升序，第二关键字为右端点降序排序，依次为 [l_1,r_1],[l_2,r_2],\cdots,[l_{|S|},r_{|S|}]。由于任意两个区间之间要么是包含关系，要么交集为空，因此答案为 \sum_{i=1}^{|S|}[i=1 \lor l_i>r_{i-1}]Sub_i。
  3. （两者都适用）每次查询后将所查询区间赋值为 0。

三种方式时间复杂度均为 O(m+(k^3+k^2\log{n}+k\log^2{n})q)。

代码

P.S.

  1. 本题读入量是真的大，强烈建议加 fread/fwrite。
  2. 由于代码巨长，所以都丢在剪贴板里了。
  3. 为了让读者感受三种处理方式的效率差异，还附上了对应的提交记录。
  4. 请注意：在第三种处理方式中，12~14 及 20~25 这 9 个测试点用时均超过了 1s，即不保证第三种处理方式能在原题 1s 的时限下通过。

第一种：处理到根路径的并集

第二种：处理子树的并集

第三种：每次查询后将所查询区间赋值为 0