Shannon’s Channel

牛客暑期多校训练营 6 A#

题目链接： Nowcoder A

题意： 给定一个排列 $p$。每次可以选择一个非端点位置 $i$，满足 $p_i$ 同时大于左右相邻元素，然后交换 $p_{i-1}$ 和 $p_{i+1}$。求经过任意次操作后，能够得到多少个不同排列。

思路： 可以从大到小处理数值，并查集维护“当前数还能去到的未知位置”。在某一步中，同一个连通块内的未知位置对当前数是等价的；选择其中任意一个位置，都不会影响之后的选择数。

当前处理数值 $i$，设它在原排列中的位置为 $j=\operatorname{pos}[i]$。执行三步：

1. find(j) 所在连通块中的所有未知位置，都是 $i$ 的候选位置。因此将该连通块大小 sz[find(j)] 乘入答案。
2. 选定 $i$ 的一个位置后，这个位置不再是未知位置，令该连通块大小减一。
3. 位置 $j$ 已经处理完毕，它左右两边的未知位置可以通过 $j$ 互相到达。因此尝试合并 $j-1$ 与 $j+1$ 所在的两个连通块。

从 $n$ 一直处理到 $1$，每一步的候选数相互独立，乘法原理给出的答案就是所有连通块大小的乘积。越界的一侧或候选数已经耗尽的连通块不参与合并。

并查集维护这些候选集合。sz 同时表示集合内尚可选择的位置数；合并时让较小集合的根挂到较大集合的根，避免合并方向导致并查集退化。

实现： 先记录每个数值的位置 pos。倒序枚举 i，找到 pos[i] 的并查集根，将该根的 sz 乘入答案并减一；若位置左右均存在，再尝试合并左右位置所属的连通块。合并前需要判断两个集合是否相同，以及是否仍有可用候选位置。

复杂度： 每个数只进行常数次查找、合并和一次乘法。配合路径压缩与按大小合并，单个测试用例的时间复杂度为 $O(n\alpha(n))$，额外空间复杂度为 $O(n)$。

另外笛卡尔树可以解释这里的候选集合为何等价：题目的操作不改变大根笛卡尔树的形态，只会交换同一结构中较小数的位置。本文不需要显式建树，并查集已经直接维护了从大到小处理时的可选位置集合。

牛客暑期多校训练营 9 D#

题目链接： Nowcoder D

题意： 给定一棵以 $1$ 为根的树。有 $m$ 个人，第 $i$ 个人从节点 $x_i$ 在时刻 $s_i$ 出发，每单位时间沿父边向根走一步。两人只要在同一时刻到达同一节点，就都会死亡；否则到达根即逃脱。求每个人能否逃脱。

思路：

先将树根定为 $1$，求出每个节点的深度 depth。对于从 $x$ 在时刻 $s$ 出发的人，记：

若他能活着走到祖先 $u$，到达 $u$ 的时刻为：

因此，在同一个节点 $u$ 汇合的两个人会相遇，当且仅当他们的 key 相同。这个 key 也可以理解为该人不受阻碍时到达根的时刻。

后序遍历整棵树。令节点 $u$ 返回一张 map<key, id>，表示 $u$ 的子树中仍然活着、且正在向上走的人；key 对应唯一的人编号。子树内部的相遇已经处理完毕，所以一张返回的 map 内不会有重复的 key。

处理 $u$ 时，先找出 map 最大的儿子并直接复用它作为 cur，再把其余儿子的 map 中的元素逐个加入 cur。最后再加入所有从 $u$ 出发的人。这就是这里的 Small to Large：始终保留最大的容器，只枚举较小容器中的元素。

加入一名 (key, id) 时分三种情况：

1. cur 中没有 key：此人暂时存活，直接记录。
2. cur 中已有 key：两人恰好在 $u$ 相遇，两人的答案都标记为死亡，并从 cur 删除这个 key。
3. 这个 key 已经发生过碰撞：之后再加入同一 key 的人也会在 $u$ 相遇并死亡。

第三种情况不能只依赖 cur。例如三个不同儿子各有一人以相同 key 到达 $u$：前两人碰撞后会从 cur 删除该键，第三人若直接插入就会被误判为存活。因此用 blocked 记录本节点已经发生过碰撞的 key；它不需要向父节点传递，因为对应的人已经全部死亡。

实现： 第一遍 DFS 计算根深度，并把每个人按起点分到 people[x] 中，记录其 key。第二遍 DFS 按后序处理节点，返回当前子树的 map<key, id>：

1. 递归得到所有儿子的 map，选出其中最大的一张作为当前 cur，无需复制，直接复用。
2. 枚举其他儿子的 map 中的每个 (key, id)，按三种情况加入 cur。这些人第一次与其他子树的人汇合的位置正是当前节点 $u$，所以在这里判定碰撞不会遗漏，也不会提前。
3. 再以同样的规则加入 people[u]。从 $u$ 出发的人与子树中的人第一次可能相遇的位置也是 $u$。
4. blocked 只在处理 $u$ 时存在；它记录的是“已经在 $u$ 死亡的到达时刻”。处理完成后，这些人不会继续向父亲移动，因此父节点既不需要也不能继承这些键。

最终根返回的 map 中的所有人都没有在任何节点相遇，答案为 1；发生过碰撞、被从 map 删除或被 blocked 拦下的人，答案为 0。

复杂度： 每个人随所在的 map 被合并时，容器规模按 Small to Large 的方式增长；总迁移次数均摊为 $O(m\log m)$。std::map 的查询、插入和删除均为 $O(\log m)$，故总时间复杂度为 $O(m\log^2 m)$，额外空间复杂度为 $O(m)$。

U41492 树上数颜色#

题目链接： 洛谷 U41492

题意： 给定一棵以 $1$ 为根的树，每个节点有一种颜色。多次询问某个节点的子树中，一共出现了多少种不同颜色。

思路： 这是 DSU on Tree 的标准应用。维护一个全局计数器 color[col]，表示当前保留的节点集合中颜色 col 出现了多少次；再维护 diff，表示计数非零的颜色种类数。

对一棵子树执行 add(u, delta) 时，遍历整棵子树：

• delta = 1 时，将所有节点加入统计。某种颜色的计数从 $0$ 变为 $1$，diff 加一。
• delta = -1 时，将所有节点移出统计。某种颜色的计数从 $1$ 变为 $0$，diff 减一。

先做一遍 DFS 求每个节点的子树大小，并找出最大儿子 heavy[u]。第二遍 DFS 按下面的顺序处理节点 $u$：

1. 先递归所有轻儿子，传入 keep = 0。每棵轻子树在算完自身答案后都会从全局统计中清空。
2. 再递归重儿子，传入 keep = 1。重子树的统计会被保留，因此此时全局计数器恰好表示重子树。
3. 将节点 $u$ 本身加入统计，再逐棵遍历轻子树，把它们的所有节点加入统计。此时统计器恰好覆盖整棵 $u$ 子树，直接令 ans[u] = diff。
4. 若当前调用的 keep = 0，最后对整棵 $u$ 子树执行一次 add(u, -1)，将它从全局统计器清空；否则保留它，交给父节点继续使用。

这里的 keep 不影响答案是否计算。无论 keep 是什么，都必须先在第 3 步得到 ans[u]；keep 只决定答案求完后是否清空当前子树的颜色统计。

为什么这样做足够快？重儿子的统计直接复用，轻子树只会在作为“轻儿子”时被整棵重新加入。沿着任意节点到根的路径，每次经过轻边，所在子树大小至少翻倍，因此一名节点至多被重新加入 $O(\log n)$ 次。这正是 DSU on Tree 中“保留重儿子、重加轻儿子”的摊还基础。

实现： 颜色编号范围不超过 $n$，可以直接用数组维护 color。第一遍 DFS 填好 size 与 heavy；第二遍 DFS 使用全局 color 和 diff，在第 3 步记录每个节点的 ans。读入询问后直接输出对应的 ans[x]。

复杂度： 预处理和回答询问分别为 $O(n)$、$O(m)$。DSU on Tree 的加减总次数为 $O(n\log n)$，因此总时间复杂度为 $O(n\log n+m)$，额外空间复杂度为 $O(n)$。