置换 & 基环树题

T1

Statement

给一个长度为 \(n(\le10^5)\) 的排列 \(\{a_i\}\)。求一个排列 \(\{b_i\}\)，使得 \(a_i=b_{b_i}\)，或输出不存在。

Solution

先把所有排列变成置换

对于任意排列 \(\{p_i\}\)，它转成置换后都是 \(i\to p_i\)，故有 \(i\to p_i\to p_{p_i}\to p_{p_{p_i}}\to...\)

所以所有原来的 \(i\to a_i\) 变成了 \(i\to b_i\to a_i\)，需要多隔一个数

若一个环的大小为奇数，可以通过每次跳两步填表，来构造出同样大小的答案；

若这个环的大小为偶数，可以把它和另一个大小相同的环镶嵌，得到答案（若没有则无解）。

T2

Statement

\(n(\le10^5)\) 个节点的带权基环树和 \(m(\le10^5)\) 组询问，每次询问两个点的最短距离。

Solution

预处理环上每个点为根向外延伸出的子树内的信息，和环上距离前缀和（断环为链）

若询问的两个点 \(u,v\) 在同一个子树内，则回答 \(dis_u+dis_v-2\cdot dis_{lca(u,v)}\)，其中 \(dis_i\) 表示 \(i\) 到 \(i\) 所在子树的根节点的距离

若不在同一子树内，需要考虑 \(u,v\) 所在子树的根节点 \(p,q\) 在环上的最短距离 \(res\)，有顺时针走和逆时针走两种走法，用前缀和算、取 \(\min\) 即可；回答 \(dis_u+dis_v+res\).

预处理 \(\mathcal O(n)\)，在线回答 \(\mathcal O(m\log n)\)，离线可做到 \(\mathcal O(m)\).

T3

Statement

给长度为 \(n(\le10^5)\) 的排列 \(\{a_i\}\)。定义移动次数为：从 \(x=1\) 开始，每次 \(x\gets a_x\)，直到 \(x\) 再次变成 \(1\) 的操作次数。你可以对排列进行 \(m(\le 2n)\) 次交换，求能达到的最多移动次数。

Solution

先转成置换，我们要让 \(1\) 所在环的大小最大

因为连边是 \(i\to a_i\)，一次交换 \(a_i,a_j\) 的效果是删除 \(i\to a_i\)、\(j\to a_j\)，添加 \(i\to a_j\)、\(j\to a_i\)

画一下图发现若 \(a_i,a_j\) 在同一个环内，效果是把它断成两个环；

若 \(a_i,a_j\) 不在同一个环内，效果是把它们合成一个环

所以我们贪心地将 \(1\) 以外的环按大小从大到小地合并到 \(1\) 所在的环，最多合并 \(m\) 次

最终输出 \(1\) 所在环的大小。

T4

Statement

给定一个 \(3\) 行 \(n(\le10^5)\) 列的表格，第一行是 \(1\sim n\) 的排列，后两行每个数 \(\in[1..n]\)。现在我们要删去一些列，之后将每一行排序，排完后需要保证每一列 \(3\) 个数相等。求删掉的最少列数。

Solution

记 \(a_i,b_i,c_i\) 表示第 \(1,2,3\) 行中 \(i\) 的出现次数。

可以发现对于所有 \(i\)，\(a_i,b_i,c_i\) 其中一个为 \(0\) 时，其中一行没有数字 \(i\)，又因为要求三行相同所以另外两行也不能有数字 \(i\)，故将所有包含数字 \(i\) 的下标元素及其所在列删除。

重复这个过程，最终 \(a_i,b_i,c_i\) 均全 \(0\) 或全不为 \(0\)，又因为第一列为排列，所以 \(a_i\) 均为 \(1\)，因为元素总数相同，故 \(b_i,c_i\) 也均为 \(1\)。此时三行排序后相同。

我们用队列优化一下，每个数最多删一次，\(\mathcal O(n)\)