{"problem":{"name":"A Certain Forbidden Index","description":{"content":"有一个长为 $n=2^k$ 的序列，基于这个序列建立了一棵[线段树](https://oi-wiki.org/ds/seg/)。现在线段树上有恰好一个节点被标记了。 你可以进行若干次询问，每次询问给定一个区间 $[l,r]$，交互库会在被修改的线段树上进行一次区间查询，你可以得知在被修改的线段树上这个区间对应的所有节点中，是否有节点被标记。 你需要在尽可能少的询问内找到这个节点。具体而言，若最","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9683"},"statements":[{"statement_type":"Markdown","content":"有一个长为 $n=2^k$ 的序列，基于这个序列建立了一棵[线段树](https://oi-wiki.org/ds/seg/)。现在线段树上有恰好一个节点被标记了。\n\n你可以进行若干次询问，每次询问给定一个区间 $[l,r]$，交互库会在被修改的线段树上进行一次区间查询，你可以得知在被修改的线段树上这个区间对应的所有节点中，是否有节点被标记。\n\n你需要在尽可能少的询问内找到这个节点。具体而言，若最优策略在最坏情况下需要 $Q$ 次询问，则你最多可以使用 $Q$ 次询问。\n\n### 交互流程\n\n你不需要，也不应该实现主函数，你只需要实现如下函数：\n\n```cpp\nstd::pair<int, int> solve(int k);\n```\n\n该函数需要在得到答案后返回一个数对 $(x,y)$，表示被标记的线段树节点所对应的区间为 $[x,y]$。\n\n你可以调用交互库提供的方法：\n\n```cpp\nint query(int l, int r);\n```\n\n传入的 `l` 和 `r` 代表询问的区间为 $[l,r]$。交互库会返回对应的结果。你需要保证 $1\\le l\\le r\\le n$。具体而言：\n\n- 当没有节点被标记时，交互库返回 $0$；\n- 当有节点被标记时，交互库返回 $1$；\n- 当询问的区间不合法时，交互库会返回 $-1$，此时你需要立即结束这组数据的交互（不是整个测试点），否则可能导致不可预知的错误。\n\n本题无询问次数限制，但过多的询问会导致时间超限，详细信息请看“数据规模与约定”。\n\n## Input\n\n下面给出样例交互库的输入输出格式：\n\n第一行输入一个整数 $T$，表示数据组数。\n\n对于每组数据，第一行输入三个整数 $k,l,r$ 代表 $n=2^k$，且将对应区间为 $[l,r]$ 的线段树节点修改。\n\n注意样例交互库不会检查输入数据的正确性。\n\n## Output\n\n对于每组数据，如果你得到的答案正确，输出一个整数表示你使用的交互次数，否则：\n\n- 若你的询问不合法，输出 `Wrong Answer [1]`；\n- 若你返回的区间不正确，输出 `Wrong Answer [2]`。\n\n[samples]\n\n## Background\n\n**这是一道函数式交互题。本题仅支持 C++ 提交。（出于某些原因，请不要使用 GCC 9 提交）**\n\n**本地编译、提交时请在程序里加入以下函数声明语句：**\n\n```cpp\nint query(int, int);\n```\n\n**任何在赛时攻击交互库而得分的行为均视为作弊。**\n\n## Note\n\n#### 样例 1 解释\n\n下面是一种可能的交互流程：\n\n| 交互库 | 选手程序 | 备注 |\n| :----------: | :----------: | :----------: |\n| 调用 `solve(2)` |  | 开始测试 |\n| 返回 $1$ | 调用 `query(1,1)` | $[1,1]$ 就是答案节点 |\n|  | 返回 $(1,1)$ | 答案正确 |\n| 调用 `solve(2)` |  | 开始下一组数据的评测 |\n| 返回 $1$ | 调用 `query(2,4)` | $[2,4]$ 对应的节点是 $[2,2]$ 和 $[3,4]$，包括了答案节点 |\n| 返回 $0$ | 调用 `query(1,4)` | $[1,4]$ 对应的节点只有 $[1,4]$，不包括答案节点 |\n|  | 返回 $(3,4)$ | 答案正确，评测结束 |\n\n### 计分方式\n\n本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。\n\n如果你找到的节点是错误的，或者你给出的询问不合法，在该测试点将会得到 $0$ 分。\n\n否则，设在一组数据中，答案最坏需要 $x$ 次询问，而你使用了 $y$ 次询问，满分为 $t$，则这组数据的分数是 $t\\times \\min\\left(1,\\mathrm{e}^{-\\frac{y}{x}+1}\\right)$。\n\n每个测试点取所有数据组中得分的最小值，向下保留两位小数。你的得分是所有测试点得分之和。\n\n### 数据规模与约定\n\n对于所有数据，保证 $1\\le k\\le 14$，$1\\le T\\le 300$。\n\n本题共 $14$ 个测试点，对于第 $i$ 个测试点，保证 $k=i$。对于 $1\\le k\\le 4$ 的测试点，满分 $10$ 分。对于 $5\\le k\\le 14$ 的测试点，满分 $6$ 分。\n\n保证在每组数据进行 $2n$ 次询问时，单个测试点内，交互库使用的时间不超过 0.6s，空间不超过 8MiB。\n\n### 下发文件说明\n\n下发文件中有一个可以通过样例的程序示例 `sample.cpp`，以及一个样例交互库 `grader.cpp`。假设你的答案文件为 `answer.cpp`，则可以使用如下命令将其编译成可执行文件 `answer`：\n\n```shell\ng++ grader.cpp answer.cpp -o answer -O2\n```\n\n实际评测时的交互库可能是自适应的，即被修改的节点可能不会在交互一开始时确定。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9683","tags":["洛谷原创","交互题","Special Judge","O2优化","构造","洛谷月赛"],"sample_group":[["2\n2 1 1\n2 3 4","1\n2"]],"created_at":"2026-03-03 11:09:25"}}