AT_kupc2020_j

Nygglatho · 2025-07-06 22:06:28 · 题解

考虑 n=4 怎么做。

对 (1,2,3),(1,2,4),(1,3,4),(2,3,4) 分别进行询问，可以发现一定能得到两个不同的中位数 L,R，令 L<R，则有一定有两组询问回答为 L，两组为 R。

然后你可以发现对于 i，在所有包含 i 的询问的回答只能是两种情况：两个 L 和一个 R，两个 R 和一个 L，如果出现两个 L 则有 a_i\le L，反之如果出现两个 R 则有 a_i\ge R。证明可以把所有情况列出来（）

显然存在排列 p 满足 a_{p_1}<L,a_{p_2}=L,a_{p_3}=R,a_{p_4}>R。不妨令满足 a_i\le L 的两个 i 为 l_1,l_2，满足 a_i\ge R 的两个 i 为 r_1,r_2，根据前面的结论我们可以通过这些询问找出 l_1,l_2,r_1,r_2。

然后你发现 l_1 和 l_2 是无法通过询问 1 区分的，r_1 和 r_2 同理，那么就用两次询问 2 区分即可。

考虑 n>4。

同样的，我们可以通过询问 1 知道 l_1,l_2,r_1,r_2 和 L,R。

对于 i，进行询问 (l_1,r_1,i)，令回答为 s，如果 L<s<R 则说明 a_i=s。

如果 s\le L，则再进行询问 (l_2,r_2,i)，令回答为 t，如果 s<t，有 a_{l_1}\le s<t=a_{l_2}，根据前面的结论 a_{l_2}=L。否则有 a_{l_2}\le t<s=a_{l_1}，有 a_{l_1}=L。