观察G1操作貌似不能再优化了，但我们可以用一些随机化算法
我们发现对于我们已经查询过的所有数中最大的数\(n_0\)，可以确定\(n\)的下界为\(n_0 \leq n\)
于是我们不妨随机选\(1000 - 2B\)个位置，取这些位置里的最大值\(n_0\)
然后我们查询位置\([1,B],B+n_0,2B+n_0,3B+n_0,...\)
结果不对当且仅当\(n_0 + B(B+1) < n\)，当\(B=400\)时，可以证明出现这种情况的概率\(< 10^{-17}\)
CF1840G2
发布时间 2023-08-22 20:24:45作者: FOX_konata