感觉是一道很好的图论题。
首先，每个点只有一个钥匙，意味着我们点集的加入顺序是固定的。我们考虑暴力枚举每个起点，维护一个栈，考虑栈顶的强连通分量是否能连到下一个目标，如果能连到，就判断是否可以缩出新的强连通分量。
这样子我们就能暴力求出每个点作为起点的答案了。
显然，如果 \(x\) 能到达 \(y\)，\(y\) 能到达 \(z\)，则 \(x\) 能到达 \(z\)。这启发我们尝试均摊。由于 \(k\) 是一个排列，所以我们可以对每个环分别处理。我们断环成链，显然不影响正确性。将原本的环变为 \(a_1\rightarrow\cdots\rightarrow a_n\rightarrow a_1\rightarrow\cdots\rightarrow a_n\)，然后从后往前考虑。如果我们当前在 \(a_i\)，已经求出了 \(a_{i+1}\) 到 \(a_n\) 的答案，尝试利用前面求到的信息快速求出答案。我们对于这个序列的一个后缀可以分成若干个区间，每个区间相当于一个链结构，这个结构由若干个强连通分量组成，实际上这个结构就是用暴力做法中栈维护出来的结构。然后对于 \(a_i\) 所在的结构，我们需要不断地向后合并这些结构，具体怎么做呢？
理清楚思路，我们现在需要合并结构，并且要合并链结构中的强连通分量，先考虑链结构如何合并。若当前 \(a_i\) 所在的链结构包括了序列区间 \([i,p]\)，如果我们想向前合并，则需要满足存在 \(a_{p+1}\) 的一个前驱在前面的链结构末尾的强连通分量中，为了判断显然我们可以贪心的找到前驱的编号最大值，现在需要考虑维护强连通分量。首先，链和强连通分量我们都可以使用并查集维护。然后我们可以注意到一个事实，如果当前 \(a_i\) 所在的链结构可以继续合并，那这个结构一定只存在一个强连通分量。
如何证明呢？我们考虑为什么加入 \(a_i\) 可以进行这么多次合并，说白了是因为我们相较于之前白白增加了 \(a_i\) 这个钥匙，所以 \(a_i\) 一定会产生贡献，如果当前这个结构不知有一个强连通分量，即除了 \(a_i\) 还有别的强连通分量，那么我们早就可以把链给合并了。
这样，我们只需要对于每一条链结构维护编号最大的有返祖边的点即可合并强连通分量。具体操作中，我们先将当前链进行强连通分量合并，然后如果这条链只存在一个强连通分量那么就继续往后合并，合并中判断 \(a_{p+1}\) 的前驱最大值是否在范围内，然后合并即可。
时间复杂度 \(\mathcal{O}(n\alpha(n))\)。
标签：连通,合并,P9150,邮箱,rightarrow,分量,我们,结构 From： https://www.cnblogs.com/lalaouyehome/p/18468382