题解：CF1526F Median Queries

BPG_ning · 2024-09-19 20:47:50 · 题解

爆标。

n^3

首先你可以 n^3 的求出每一对的答案，如果 ask(a,b,c) = 1 那么 p_a,p_b,p_c 在值域上是相邻的，因为序列是较长的，所以一定有解，并且保证 p_1 < p_2 ，所以解唯一（因为将 p_i \gets n-p_i+1 之后查询结果都不变，若不保证这一点就会有两个解）。

这个 n^3 做法能告诉我们这题是可做的。

n^2

考虑对于一个点 {pos} 求出其他点的相对位置。

先考虑求 |p_{pos} - p_i| ，钦定 p_{pos}<p_{i} 。

定理一：发现一个 ask(a,b,c) 在数轴上的意义是按顺序排列的三点的相邻两点的距离较大值。

定理二：对于每个 p_{pos}<p_{j}<p_{i} 的 j 的 ask(i,j,pos) 一定小于不在区间里的 j' 的 ask(i,j',pos) 。

定理二证明：

根据定理一：

我们抛开求每个点到一个点的距离的想法，考虑求极值。

具体来说如果我们找到了 p_i=1,p_j=2 ，那么 p_k=ask(i,j,k)+2 ，我们就可以用 n-2 次询问求出答案！

现在我们需要用 C+n+2 次询问找到这个极值。

假设我们有一个较短的区间 [p_l,p_r] ，由于序列是较长的，根据定理一，我们可以找到所有 ask(i,l,r) 的最大和次大的 i 并认为他们是极值，因为他们是在数轴上距离 [p_l,p_r] 最远的点，自然是极值。

而且我们能发现较短的区间的定义是 len \leq \frac{n}{3} ，因为若区间长 > \frac{n}{3} ，那么可能存在两端的极值 ask(l,r,i) = | p_r-p_l | ，这样你就无法区分极值了。

所以如果我们找到一个较短的区间，用 n-2 次询问就可以找到极值！

考虑用 C+4 次询问找到任意较短的区间，一个很好的想法就是随机化，每次随一个 a,b,c ，若 ask(a,b,c) \leq \frac{n}{6} ，那么这三点中任意两点构成的区间都是较短的！

证明：

令 p_a<p_b<p_c .

那么根据定理一有 \frac{n}{6} \geq ask(a,b,c) = \max(p_b-p_a,p_c-p_b) \geq \frac{p_c-p_a}{2} .

所以 p_c-p_a \leq \frac{n}{3} .

我们再抛开找极值的思路。

考虑将找极值弱化，只要找到一对相邻的元素，即长度为 1 的区间。

怎么找呢？根据 n^2 做法，考虑 [p_1,p_2] 这个区间，先用 n-2 次询问算出这个区间长度 len ，根据定理二能知道那些点在区间里面，即满足 p_1 < p_i < p_2 。

能把区间内的每一个元素求出来吗？考虑随便找到一个 {mid} （区间长为奇数的时候不关心这是靠左的中点还是靠右的中点），用 len 次询问同理得出 p_2-p_{mid} ，再次根据定理二得知那些点在区间 [p_{mid},p_2] 里！由于这是中点，所以这样你就可以知道区间里每一个 ask(1,2,i) 是 p_2-p_i 还是 p_i-p_1 。

我们用 len+n-2 次询问，但是求出了区间内的所有点，我们在区间里找到 pos 满足 p_{pos}=p_1+1 ，那么我们就找到了一对相邻的元素，满足 ask(1,pos,i) = p_1-p_i 或 p_i-p_{pos} ，这是显然的。

我们对于不在区间里的 n-len-2 个点询问 ask(1,pos,i) ，如果我们知道这个点是 p_i<p_1 还是 p_{pos}<p_i 我们就做完了！

我们结合 ask(1,2,i) 进行分类讨论：

1.若 ask(1,2,i)=len,ask(1,pos,i)<len ，那么 p_i<p_1 。

2.若 ask(1,2,i)=len,ask(1,pos,i)>len ，那么 p_i>p_{pos} 。

3.若 ask(1,2,i)>len,ask(1,pos,i)=ask(1,2,i) ，那么 p_i<p_1 。

4.若 ask(1,2,i)>len,ask(1,pos,i) \ne ask(1,2,i) ，那么 p_i>p_{pos} 。

5.若 ask(1,2,i)=len,ask(1,pos,i)=len ，此时你无法只通过这两种询问区分 p_i=p_1-len 和 p_i=p_{pos}+len 。因为这种情况只会出现一次，我们可以询问 ask(1,mid,i) 来区分他们（总之是好做的）。

这部分读者根据定理一手玩即可发现。