斗胆在 QOJ 上写一篇题解？

sol 1：$O(n\ln n)$

这是我的做法，问了一圈好像大家都是这个做法，但是在实现上有常数优劣之分，我的实现是最菜的/ll

观察询问次数大概就是 $O(n\log n)$ 这个量级，所以想当然的去二分。

对于已经确定值的位置我们就不需要考虑了，对于剩下不确定值的位置我们随机打乱对应的值，直到这些位置中存在 $p_i=q_i$。

维护当前可能有 $p_i=q_i$ 的位置集合 $S$，将 $S$ 均分成两个集合 $A,B$，我们想判断 $A$ 中是否有位置满足 $p_i=q_i$，当然是保证 $A$ 不动，然后想办法让 $B$ 以及其他位置不可能有 $p_i=q_i$。但是仔细思考一下，好像我们没有办法保证这一点。

这个时候我的想法是，能不能尝试用一下已知量呢？

假设我已经得到 $k$ 个位置以及其真实值，那么查询的时候只需要把 $B$ 集合的位置放这些已知的值，而这些已知的位置上放 $B$ 集合中的值，不难发现这样 $B$ 集合以及这 $|B|$ 个已知的值都不会产生影响，很容易就能判断 $A$ 中是否有 $p_i=q_i$ 了！

但是这要保证 $|B|\le k$，我们考虑令 $B$ 集合的大小为 $\min({|S|\over 2},k)$，那么一次询问至少能排除掉 $\min({|S|\over 2},k)$ 个数。

于是已经知道 $i$ 个确定的位置和值的时候，需要的询问次数是：

$$ \sum_{i=1}^n \max({n\over i},\log_2(i))=O(n\ln n) $$

当然这个做法需要先有至少 $1$ 个已知的位置，这里大家就各显神通一下，做法很多。

因为每次都要先随机出相等的位置，这里需要常数次，所以还有 $O(n)$ 的常数，我的实现大概是 13000 次左右。

不过有一些奇技淫巧，比如随出的排列至少有 $2$ 个相同的位置时才二分递归找位置，这样能够快速增加前期已知的位置数量，代价是询问的常数次变大，据说加入各种卡常可以卡到 10500 次左右。

sol 2：$O(n\log n)$

回到 sol 1 最开始的想法，事实上不需要已知值我们也可以做到 $O(\log n)$ 次找到一个已知的位置。

这里需要补充一点，随机排列是错排的概率是 $1\over e$，所以期望 $e$ 次就能随出错排。

将 $S$ 均分为 $A,B$ 之后，我们可以随机打乱 $A$ 集合多次，如果相等的位置变少就说明 $A$ 中必然有相同的位置，递归下去找即可。

但是具体打乱多少次很有说法，因为要做 $O(n\log n)$ 次判定，据官解的说法设定阈值在 $O(\log n)$ 次才比较靠谱，这样复杂度就是 $O(n\log^2 n)$ 了，非常劣。

这时一个很巧妙的想法是，我们交替打乱 $A,B$ 集合！这样的好处是不需要设定阈值了，只要打乱一个集合之后答案变小，那么这个集合中就有正确的位置，直接递归就好！此时每次递归都只需要打乱常数次，期望复杂度是 $O(n\log n)$ 的，据官解说大概是 15500 次左右。

当然这里也可以利用一下已知信息，如果要判定 $A$ 集合是否有 $p_i=q_i$ 的位置，优先将已知的值填在 $A$ 集合，剩下的再随机打乱，这样常数会小一些。

sol 3：官解

考虑把 sol1 和 sol2 拼起来！可以发现 sol1 和 sol2 并不冲突，都是在把剩余可能的集合变小。

所以设定一个阈值 $p$，当 $k\ge |S|\times p$ 的时候跑 sol1，$k<|S|\times p$ 的时候跑 $sol2$，这样看上去就很优，因为 sol1 前期的劣势被 sol2 所弥补了！据官解说，$p\in[0.1,0.2]$ 时比较优秀，但是我不知道为什么我的实现 $p$ 根本不重要，$p\in [0.05,0.5]$ 都只是常数上的差异。

这个做法我和另外一位同学的实现都是 10500 次左右，不知道官解怎么做到 $9200$ 次的。

sol 4：$n\log_2 \lceil{n\over 2}\rceil+\lceil{n\over 2}\rceil+O(1)$

一个与之前所有想法完全不同的做法。

随出一个错排 $q$，可以发现 $q$ 到 $p$ 之间只差一个置换。对于每个元素 $x$，若其在 $q,p$ 的出现位置分别是 $a_i,b_i$，连边 $(a_i,b_i)$，最终图会形成一些环，并且没有自环。

可以发现，如果我们交换 $q_x,q_y$ 后答案变大，那么就可以确认 $(x,y)$ 是图的一条边，据此就得到了一个简单的 $O(n^2)$ 做法。

但是我们显然可以并行询问，考虑每次选择一个边集 $E$，只要 $E$ 中每条边不共端点，那么不同边之间就互不影响，每次询问可以知道 $E$ 和图的边集的交集大小。

通过 zig-zag pattern 将完全图划分成 $n-1/n$ 组匹配，每次在匹配中二分，这部分询问次数是 $\le n\log_2 {n\over 2}\le 9000$ 次的。

而最后我们得到了图的边集，还要确认每个环的方向，这个再做一次询问就好了，环数是 $\le {n\over 2}\le 500$ 次的。

看起来次数会刚好爆一点点，但是注意到排列是随的，置换环的个数期望实际上是 $\ln n$，所以 Part2 根本问不到 $500$ 次，我的实现大概是 9100 次左右。

而最后还可以再加入一个减枝：当一条边 $(x,y)$，$x$ 或 $y$ 已经确定两条边的时候，这条边就不可能再成为答案了，可以直接从边集中删去。

这个减枝的效果立竿见影，我的实现平均次数是 7600 次左右，这也应该就是官解说的爆标做法。