菜王的 blog

记忆中每次场上想出踩 std 的做法的时候都会因为各种原因没有场切，怎么回事呢？？？

考虑假如我们知道一对满足 $p_x < p_y$ 的 $(x, y)$，那么可以通过询问 $(x, y), (x, z), (y, z)$ 来得知 $p_x, p_y, p_z$ 之间的大小关系，并且假设 $p_x, p_y, p_z$ 的中位数为 $o$，那么有 $a_o = Q(x, y) + Q(x, z) + Q(y, z) - 2\max(Q(x, y), Q(x, z), Q(y, z))$。

那么我们可以考虑 $i$ 从小到大枚举的同时动态维护 $p_1, p_2, \dots, p_i$ 的顺序。

假设 $p_{id_1} < p_{id_2} < \cdots < p_{id_i}$，其中 $id$ 为一个 $1 \sim i$ 的排列，并且我们已经提前知道了每个 $Q(p_{id_j}, p_{id_{j + 1}})$，以及每个 $a_{p_{id_j}}$（$1 < j < i$）的值。最初 $id = [1, 2]$，并且查询一次 $Q(1, 2)$。

设 $sum = Q(id_1, id_i)$（这可以通过已知量推出），$sl = Q(id_1, i + 1), sr = Q(id_i, i + 1)$。考虑分讨：

• $sl = \max(sl, sr, sum)$：此时 $i + 1$ 插入到 $id$ 最右边，$a_{p_{id_i}} = sr + sum - sl$。
• $sr = \max(sl, sr, sum)$：此时 $i + 1$ 插入到 $id$ 最左边，$a_{p_{id_2}} = sl + sum - sr$。
• $sum = \max(sl, sr, sum)$：此时可通过 $sl$（或 $sr$）二分出 $i + 1$ 插入在哪两个数之间，$a_{p_{i + 1}} = sl + sr - sum$，并能重新推出 $i + 1$ 与其相邻两个数的询问结果。

最后 $a_1, a_n$ 可以直接推出，对 $id$ 求一个逆排列即可得到 $p$。最开始询问出 $Q(1, 2)$，接下来对于 $i$ 从 $3$ 到 $n$ 都询问两次，一共 $2n - 3$ 次。由于此题数据范围较小，暴力插入即可通过。