题解 CF1764G Doremy's Perfect DS Class (Extra)

题意

交互库有一个 \(1\sim n\) 的排列 \(p\)，你每次可以想交互库给定三个整数 \(l,r,k(1\le l\le r\le n,1\le k\le n)\)，交互库会返回 \(\lfloor p_l/k\rfloor,\lfloor p_{l+1}/k\rfloor,\dots,\lfloor p_r/k\rfloor\) 中不同数的个数。你需要在 \(\lceil 2n\log_2n\rceil\) 次询问内确定整个数组。

\(3\le n\le 1024\)。

题解

可以先尝试着确定一些简单的值，不难发现 \(n\) 的值很容易从 \(k=n-1\) 的情况下二分出来得到位置，于是一种朴素的想法就是依次找到 \(n,n-1,\dots,1\) 这些数的位置。但是这样想下来会发现完全无法操作，因为在二分求解 \(x\) 的位置时候很有可能要把大于 \(x\) 的这些数全部排除在外，排除掉这些数可能就会分割出很多区间，操作次数很难优于 \(O(n^2)\)。

找最大的数不好我们可以尝试找一下最小的数 \(1\)，这也是原题三个 version 的要求。要找 \(1\) 想到可以让 \(k=2\) ，于是发现 \(k=2\) 相当于 \((2,3),(4,5),(6,7),...\) 这些数对匹配，然后通过一些简单计算相当于查询区间匹配数量。

当 \(n\) 为奇数的时候，\(1\) 是唯一一个单出来没有其它匹配的数。考虑二分 \([l,r]\)，确定 \(1\) 是在 \(m=\lfloor(l+r)/2\rfloor\) 的左边还是右边。可以分别查询 \([1,m]\) 和 \([m+1,n]\) 两个区间，总匹配数量我们是知道的，而匹配对要么只在左边要么只在邮编要么跨越两边，由此两边不断消去匹配对直到唯一一个区间剩下的一个数就是 \(1\) 了。

而 \(n\) 为偶数的时候，\(n\) 和 \(1\) 都是单出来的，不过前面我们可以简单找到 \(n\) 的位置，所以很好区分 \(n\) 和 \(1\)，我们便实现了不超过 \(\lceil3\log_2 n\rceil\) 次找到 \(1\) ，而三个 version 也只是在进行没有太大意义的常数优化罢了。

找到了 \(1\) 之后考虑依次确定 \(2,3,\dots,n\) 吗？容易发现比从大到小确定更难了。既然按照数字大小依次确定没有戏了，不妨考虑按照相对位置尝试一下。如果 \(1\) 在位置 \(x\)，那么位置 \(x-1\) 的数字突然发现变得意外地好求了！因为只要通过两个数绑在一起除以 \(k\) 下取整，就可以判断是小于 \(k\) 还是大于等于 \(k\) 了。然后考虑 \(x-2\) 的位置，和 \(1\) 不是相邻的有点不太好处理，而想到 \(x-3\) 后面就更加困难了，所以我们需要一个更加具有普适性的思路来依次确定这些数字。

考虑和 \(1\) 相邻我们究竟用到了什么性质，就是除以 \(k(k\ge 2)\) 下取整后 \(1\) 必然会变成 \(0\)，然后我们相当于就只是在判断这个数除以 \(k\) 是不是也是变成 \(0\) 罢了。由此启发我们这样的一个思路，如果已经求出来了 \(x,x-1,\dots,x-t+1\) 这些位置的数，现在要求 \(p_{x-t}\)。然后我们二分了一个 \(k(k\ge 2)\)，我们可以找到 \(x-t\) 后面第一个小于 \(m\) 的位置 \(x-s\)，这个位置一定存在因为 \(p_x<k\)，由此我们知道 \(\lfloor p_{x-s}/k\rfloor=0\)，接着我们需要判断的是是否有 \(\lfloor p_{x-t}/k\rfloor=0\)，而我们知道 \(\forall x-t<i<x-s,\lfloor p_i/k\rfloor\ne 0\)，所以我们就可以查询 \([x-t,x-s-1]\) 和 \([x-t,x-s]\) 两个区间进行比较得到 \(p_{x-t}\) 与 \(k\) 的相对大小。这样我们可以通过 \(\lceil 2\log_2n\rceil\) 次操作找到一个与 \(x\) 不相邻的位置的值，而相邻的可以 \(\lceil\log_2n\rceil\) 确定。