找到排列中的 1

题目大意

评测机保存一个秘密的 \(1\sim n\) 的排列 \(a\)，允许你进行两种询问：

1. 询问 \(i,j,k\)，评测机告诉你是否有 \(k\mid(a_i-a_j)\)
2. 询问 \(i,j\)，评测机告诉你是否有 \(a_i<a_j\)

其中，询问 \(2\) 最多进行一次，询问 \(1\) 可以进行任意次，但是不能超时。

你需要确定 \(1\) 在排列中的位置，即找到 \(i\)，使 \(p_i=1\)。

时间限制 \(2s\)，\(n\le 10^6\)。

Algo 1

考虑暴力，\(O(n^2)\) 询问排列中任意两个不同位置，显然只有询问到 \(1,n\) 时差值能被 \(n-1\) 整除。

进行一次询问 \(2\) 确定大小即可。

Algo 2

\(\text{Algo 1}\) 提供了一种思路，即，如果我们知道一组数的最大值最小值的差，我们可以 \(O(n^2)\) 的询问最大值和最小值，不能确定顺序。

考虑对原序列进行分治，我们可以通过询问每个位置与位置 \(1\) 的差是否被 \(2\) 整除将原序列分成两组。每组中任意两数的差可以被 \(2\) 整除，但不一定被 \(4\) 整除。

如果 \(n\) 为奇数，那么两组数有一组较多，这一组一定均为奇数，\(1\) 和 \(n\) 一定都在这一组，我们可以递归做下去。

一种处理方法是定义一个阈值 \(S\)，递归到大小为 \(S\) 的时候暴力查出区间最大最小，保存到另一个数组，最后在这个数组暴力查最大最小。

递归的复杂度是 \(O(n\log n)\) 的，可以忽略不计，最终将取得 \(O\left(\dfrac{n}{S}\right)\) 块，每块长 \(O(S)\)，总的暴力复杂度是 \(O(nS)\) 的。

由于每个块会向数组加入 \(O(1)\) 个数据，最终数组的长度是 \(O\left(\dfrac{n}{S}\right)\) 的，暴力复杂度 \(O\left(\dfrac{n^2}{S^2}\right)\)。

总复杂度 \(O\left(\dfrac{n^2}{S^2}+nS\right)\)，由均值不等式，取 \(S=\sqrt[3]{n}\) 时复杂度最优，此时复杂度为 \(O(n^{4/3})\)。

Algo 3

上面那个做法略笨，因为我们不必将合并留到最后，如果在递归回溯过程中合并，单次计算是 \(O(1)\) 的，最终复杂度 \(O(n\log n)\)

Algo 4

最开始可以随意选一个数，\(O(n\log n)\) 二分和这个数差最大的数，显然这个数非 \(1\) 即 \(n\)，\(O(n)\) 扫一遍与这个数差 \(n-1\) 的数即可。