自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:36:24，当前版本为作者最后更新于2022-02-03 11:18:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Subtask 1

你不会吗？

你真的不会吗？

Subtask 2

要拿到这一档分，我们需要来看看操作二。

给出常数 $a,b$：表示现在已知存在有穷个 $f:\R\rightarrow\R$，使得 $f(v_a)\ne f(v_b)$。

有穷个函数？为什么呢？我不是应该想有多少个函数就有多少个函数吗？只需要让 $f(v_a)\ne f(v_b)$ 就可以了，它们的取值任意，那不是有无穷种函数吗…

且慢。$v_a\ne v_b$ 时确实是这样，但 $v_a=v_b$ 时呢？

我们发现当且仅当 $v_a=v_b$ 时，不存在符合条件的函数——也就是说，存在“有穷个”（零个）符合条件的函数。

于是操作二翻译过来就是：

给出常数 $a,b$：表示现在已知 $v_a=v_b$。

那么再看原题，不难发现就是个并查集的板子，直接做就好了。

Subtask 3

现在来看操作一：

给出常数 $a,b,c,d$：表示现在已知存在无穷个 $f:\R\rightarrow\R$，使得 $\frac{f(v_a)}{f(v_b)}=\frac{v_c}{v_d}$。

沿用上面的思路，我们对 $v_a=v_b$ 和 $v_a\ne v_b$ 两种情况分别讨论。

$v_a\ne v_b$

那么对于任意可能的 $v_c,v_d$，我们都只需要使 $f(v_a),f(v_b)$ 的取值满足上面的等式即可，当然有无穷多个函数。也就是说此时这个条件什么用都没有。

$v_a=v_b$

首先根据初中数学 $f(v_b)\ne 0$。其次由于 $v_a=v_b$，则必有 $f(v_a)=f(v_b)$。联系上面的等式，也就是说 $v_c=v_d$ 恒成立。

于是操作一翻译过来就是：

给出常数 $a,b,c,d$：表示若 $v_a=v_b$，则 $v_c=v_d$。

转换为并查集的操作，也就是说当 $v_a,v_b$ 这两个变量所对应的点连通时，我们就需要在 $v_c,v_d$ 中间连一条边。由于本 Subtask 中操作总数并不多，我们每加入一条边后对前面每一个操作一都检查一下也可以通过，时间复杂度 $O(n^2)$。

Subtask 4

遇到操作一时，如果 $v_a,v_b$ 已经连通，则直接把 $v_c,v_d$ 相连即可；否则，我们分别向 $v_a,v_b$ 所在的连通块添加一个本次操作序号的标记（用一个 $set$ 维护），表示当以后将这个连通块与其它合并时需要检查一下有没有满足这个操作一的条件。然后由于这样的连接是双向的，我们合并两个连通块时只需要对一个连通块中所有的标记检查一次即可。此时不难发现我们可以套用启发式合并的思想，每次选择标记较少的连通块检查，即可通过本题。时间复杂度 $O(n\log^2n)$。

此外要注意一次合并可能会触发多次新的合并，可以用递归或者队列实现。

ametus.h / tears.cpp