CF2237E 题解

思路

经典地，对于排列 $p$，连边 $i\rightarrow p_i$ 形成若干个置换环。

称 $i\rightarrow a_i$ 为红边，$i\rightarrow b_i$ 为蓝边；设 $a$ 的逆排列为 $ia$（满足 $ia_{a_i}=i$，即 $ia_i$ 为 $i$ 在红色置换环上的前驱）。

如果某个红色置换环中存在 $b$ 不为 $-1$ 的元素 $i$，整个置换环的 $b$ 值会同时被确定（或发现无解）：因为存在红边 $ia_{i}\rightarrow i$ 和蓝边 $i\rightarrow b_i$，按照题目限制，应当存在一条新的蓝边 $ia_i \rightarrow ia_{b_i}$，循环下去就能确定整个置换环的 $b$ 值。

手玩之后会发现这实质上是两个大小相同的红色置换环的对应关系：

如果一个红色置换环中连出了两条到不同红色置换环的蓝边，或是连到了与自己大小不相等的红色置换环，就直接输出无解。

处理完这些确定的环之后，考虑 $b$ 全部为 $-1$ 的环。这个时候的自由度很高，同样是对每个红色置换环匹配一个大小相同的红色置换环（可以是自己），并且环上的对应关系也可以随意安排。

题目限制要求 $b$ 字典序最小，于是我们直接将所有大小相同的未被匹配的环和待匹配的环按环上元素的最小值分别排序，然后一一匹配即可，匹配时应将两个环上的最小值相对应。

实现上稍微有点麻烦，写一个函数 $\operatorname{f}(x,y,i,j)$，用来完成将环 $x$ 与 $y$ 进行匹配，$x$ 上第 $i$ 个元素与 $y$ 上第 $j$ 个元素对应的任务会简单不少。

复杂度 $\mathcal{O}(n)$，不带排序的 $\log$ 因为找环可以直接按下标从小到大找。