Codeforces Round #755 (Div. 2) Guess the Permutation 题解 (Java/C++)

题解

我们考量查询[x, n]的图像。也就是说，随着x的变化，查询(? x n)的结果的变化。

也就是说，当$x\leq i$时，(? x n)=(? 1 n)。而当$x \geq k$时，(? x n)=0。
而因为x=j-1时，因为此时a[j-1]<a[y]（其中$j\leq y \leq k$），所以(? j-1 n)=(? j n)。除此处之外，其他位置图像都是严格单调递减的。

于是很显然的，i和k可以通过二分搜索找到。
但是这样会面临两个问题：1. 根据n的规模，每次二分都需要30次查询，同时搜索i和k会需要60次查询。2. j的值如何求解？

不难发现，当$x\geq j$时，对于$\text{(? x n)}=\frac {len\cdot (len -1)} 2$中的y必有整数解。而当$x< j-1$时，y大概率不存在整数解（以i=1， j=10，k=12，x=7为例，(? 7 12)=6，此时y依然有整数解，但这种情况属于少数情况）。
于是，当我们发现一次查询后的y有整数解时，我们可以根据x和y计算出k的值，k=x + y -1。
但考虑到上面说的少数情况，我们可以通过查询(? x+y-2 x+y-1)来判断，如果查询结果是1，那么k=x+y-1。如果查询结果是3，可能是x=j-1，因此我们再尝试一次即可。

同理，当x=j时，不仅(? x n)有整数解，(? 1 n) - (? x n)也必有整数解，且(? x-1 n)=(? x n)。当x=j-1时，(? 1 n) - (? x n)必有整数解，且(? x-1 n)=(? x n) + 1。

于是我们就能判断x到底是在j-1左边，还是在j右边，还是x就是j或j-1。

代码

Java

C++