2024-10-03-solution-ucup-season3-stage10-C

The 3rd Universal Cup. Stage 10: West Lake Problem C Permutation 题解

场上为队伍做出的唯一贡献。

考虑其实你直接每一个数去二分总次数是 $n\log n = 10000$ 其实差的不是太多了。

我的想法是，但是感觉你每一个数每一个数的去做非常的亏。 然后每次你随机拉出两个数，两个一起做下去。你去暴力询问左边那个数的可能区间的左半边拼上右边那个数可能区间的右半边，如果这是询问为 $2$ 或者 $0$ 我们就省了一次操作。这很好，大致可以达到 ${3\over4}n \log n$ 次操作。我以为如果你剪剪枝还是能过得。写出来寄了。

然后扔给 @yhddd 一看发现这样非常亏，你不如直接整体二分，然后你要是左半边填满了右边的数也就直接确定了。这样子做比较优秀，而且可以让你可以尽可能多的拉出两个数，尽管这东西理论上还是 ${3\over4}n \log n$ 次操作的。这是可过的。尽管要是你随机多几次还是有可能超过次数限制。code。

其实正解也很简单，赛时也几乎想到了，但是没想到这样子做可以降低次数。就是你发现其实如果询问结果为 $1$ 的话那么这两个数一定属于同一半边。所以你直接合并起来，继续操作。这样做就可以严格低于 $6666$ 次操作了。代码没写。过了就行。