CF1764G3 Doremy's Perfect DS Class (Hard Version)

本题与另外两个版本的唯一区别在于最多允许的查询次数。在本版本中，你最多可以进行 $ \mathbf{20} $ 次查询。只有当你解决了所有版本的问题后，才能进行 Hack。 这是一个交互题。 “大家好！Doremy 的完美数据结构课马上开始啦！想要拥有和我一样高的智商就来努力吧！”在今天的数据结构课上，Doremy 正在教大家一个强大的数据结构——Doremy 树！现在她给你出了一道小测验，以证明你在认真听课。 给定一个长度为 $ m $ 的数组 $ a $，Doremy 树支持查询 $ Q(l,r,k) $，其中 $ 1 \leq l \leq r \leq m $ 且 $ 1 \leq k \leq m $，该查询返回数组 $ \left[\lfloor\frac{a_l}{k} \rfloor, \lfloor\frac{a_{l+1}}{k} \rfloor, \ldots, \lfloor\frac{a_r}{k} \rfloor\right] $ 中不同整数的个数。 Doremy 有一个秘密排列 $ p $，它是 $ 1 $ 到 $ n $ 的一个排列。你可以进行查询，每次查询你给出 $ 3 $ 个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），你会收到 $ Q(l,r,k) $ 在数组 $ p $ 上的值。你能否在最多 $ \mathbf{20} $ 次查询内，找到下标 $ y $（$ 1 \leq y \leq n $）使得 $ p_y=1 $？ 注意，排列 $ p $ 在你进行任何查询之前就已经确定。

你首先需要读取一个整数 $ n $（$ 3 \le n \le 1024 $），表示排列的长度。 每次查询时，你应输出 - "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $） 单独占一行。每次查询后，你应读取一个整数 $ x $，表示在 $ p $ 上 $ Q(l,r,k) $ 的值。在本题版本中，你最多可以进行 $ 20 $ 次这样的查询。要给出答案时，你应输出 - "! $ y $"（$ 1 \leq y \leq n $） 单独占一行，其中 $ p_y=1 $。每次输出查询或答案后，不要忘记输出换行并刷新输出缓冲区，否则会导致 Idleness limit exceeded。为此，你可以使用： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $），表示排列的长度。 Hack 的第二行包含 $ n $ 个互不相同的整数 $ p_1,p_2,\ldots,p_n $（$ 1 \le p_i\le n $），表示排列。

见输入格式说明。

示例中的排列为 $ [3,5,2,1,4] $。 示例交互过程如下（仅为说明，空行仅为清晰起见）： - 第一次查询，$ \lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=0 $，所以答案为 $ 2 $。 - 第二次查询，$ \lfloor\frac{2}{3}\rfloor=0,\lfloor\frac{1}{3}\rfloor=0,\lfloor\frac{4}{3}\rfloor=1 $，所以答案仍为 $ 2 $。 - 第三次查询，$ \lfloor\frac{2}{5}\rfloor=0,\lfloor\frac{1}{5}\rfloor=0 $，所以答案为 $ 1 $。 - 第四次查询，$ \lfloor\frac{2}{2}\rfloor=1,\lfloor\frac{1}{2}\rfloor=0,\lfloor\frac{4}{2}\rfloor=2 $，所以答案为 $ 3 $。 在 $ 4 $ 次查询后得到了正确答案，因此该过程判为正确。 由 ChatGPT 4.1 翻译