[Mivik Round / 梦境彼岸] [题解] 泪光 Tears

· · 题解

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