P15829 [JOI Open 2014] 秘密 / Secret

Anna 发明了一种神秘的二元运算 $\star$。对于小于等于 $1\,000\,000\,000$ 的非负整数 $x, y$，运算结果 $x \star y$ 也是一个小于等于 $1\,000\,000\,000$ 的非负整数。这个运算 $\star$ 是**结合**的。即，对于任意小于等于 $1\,000\,000\,000$ 的非负整数 $x, y, z$，等式 $(x \star y) \star z = x \star (y \star z)$ 恒成立。这个值可以简单地记作 $x \star y \star z$。 Anna 打算和 Bruno 玩一个游戏。她让 Bruno 来猜这个运算 $\star$。她首先向 Bruno 展示了 $N$ 个整数 $A_0, A_1, \dots, A_{N-1}$。然后，她向 Bruno 提出了若干个如下形式的询问：“$A_L \star A_{L+1} \star \cdots \star A_R$ 的值是多少？” Bruno 说没有提示的话很难玩这个游戏。于是 Anna 决定给他一些提示。每次提示的过程如下：Bruno 选择两个数 $x, y$ 来询问 $x \star y$ 的值，Anna 则会告诉他 $x \star y$ 的结果。他可以在游戏开始时，也就是已知整数 $A_0, A_1, \dots, A_{N-1}$ 的情况下请求提示。他也可以在 Anna 向他提出某个询问时请求提示。当然，他希望尽量减少请求提示的次数。因为他希望表现得好像几乎知道关于运算 $\star$ 的一切，所以他尤其希望减少在收到询问之后请求提示的次数。 ### 任务 编写一个程序，实现 Bruno 的策略，即通过请求提示来正确回答 Anna 的询问。 ### 实现细节 你需要编写一个程序，实现请求提示并回答 Anna 询问的策略。你的程序必须通过 `#include "secret.h"` 包含头文件 `secret.h`。 你的程序需要实现以下过程。 - `void Init(int N, int A[])` 该过程在程序开始时仅被调用一次。参数 $N$ 是 Anna 展示的整数的数量。参数 $A$ 是一个长度为 $N$ 的数组。元素 $A[0], A[1], \dots, A[N-1]$ 即为她展示的整数 $A_0, A_1, \dots, A_{N-1}$。 - `int Query(int L, int R)` 当 Anna 向 Bruno 提出一个询问时，该过程被调用。这意味着她在询问 $A_L \star A_{L+1} \star \cdots \star A_R$ 的值（$0 \leq L \leq R \leq N - 1$）。 该过程应返回 $A_L \star A_{L+1} \star \cdots \star A_R$ 的值。 你的程序中可以调用以下过程。 - `int Secret(int X, int Y)` 当 Bruno 请求一个提示时，调用此过程。这意味着他在询问 $X \star Y$ 的值。参数 $X$ 和 $Y$ 必须是满足 $0 \leq X \leq 1\,000\,000\,000$ 和 $0 \leq Y \leq 1\,000\,000\,000$ 的整数。如果调用此过程时传入的参数不满足此条件，你的程序将被判定为 **Wrong Answer [1]** 并终止。 该过程返回 $X \star Y$ 的值。 ### 编译与测试运行 你可以从竞赛网页下载一个归档文件，其中包含一个用于测试你程序的样例评分器。该归档文件还包含一个你的程序的样例源文件。 样例评分器由一个源文件组成，文件名为 `grader.c` 或 `grader.cpp`。例如，如果你的程序是 `secret.c` 或 `secret.cpp`，你可以运行以下命令来编译你的程序。 - **C** ```bash gcc -O2 -std=c11 -o grader grader.c secret.c -lm ``` - **C++** ```bash g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp ``` 编译成功后，会生成可执行文件 `grader`。 请注意，实际评测使用的评分器与样例评分器不同。样例评分器将作为单个进程运行，它会从标准输入读取输入数据，并将结果写入标准输出。 ### 样例评分器说明 样例评分器假设 Anna 的秘密二元运算 $\star$ 为 $x \star y = \min\left\{x + 2\left\lfloor \frac{y}{2} \right\rfloor, 1\,000\,000\,000\right\}$。这里 $\lfloor r \rfloor$ 表示不超过 $r$ 的最大整数。请注意，这与实际评分器的行为不同。

样例评分器从标准输入读取以下数据。 - 第一行包含一个整数 $N$，表示 Anna 展示的整数的数量。 - 第二行包含 $N$ 个以空格分隔的整数 $A_0, A_1, \dots, A_{N-1}$，即 Anna 展示的整数。 - 第三行包含一个整数 $Q$，表示 Anna 提出的询问数量。 - 接下来的 $Q$ 行中，第 $(j+1)$ 行（$0 \leq j \leq Q - 1$）包含两个以空格分隔的整数 $L_j$ 和 $R_j$（$0 \leq L_j \leq R_j \leq N - 1$）。这表示在第 $(j+1)$ 个询问中，Anna 询问的是 $A_{L_j} \star A_{L_j+1} \star \cdots \star A_{R_j}$ 的值。

程序成功终止后，样例评分器会将每次 `Query` 调用返回的值按行写入**标准输出**，每行一个。同时，它还会向**标准错误**输出以下信息。 - 如果你的程序被判定为 **Wrong Answer [1]**，它会输出 “Wrong Answer [1]”。（实际输出不含引号。） - 如果你的程序未被判定为 **Wrong Answer [1]**，它会输出在过程 `Init` 中调用 `Secret` 的次数，以及在每次调用过程 `Query` 的过程中调用 `Secret` 的最大次数。

### 样例交互 以下是样例评分器的一个样例输入，以及各过程之间交互的示例。注意，如果使用样例评分器，以下返回值是正确的。 | 输入 | |----------------| | 8 | | 1 4 7 2 5 8 3 6 | | 4 | | 0 3 | | 1 7 | | 5 5 | | 2 4 | | 调用 | 返回值 | |-------------------------|--------| | Init(8, [1, 4, 7, 2, 5, 8, 3, 6]) | 无 | | Query(0, 3) | 13 | | Query(1, 7) | 32 | | Query(5, 5) | 8 | | Query(2, 4) | 13 | 在过程 `Init` 或过程 `Query` 中可以调用过程 `Secret`。例如，当调用 `Secret(4, 7)` 时，如果使用样例评分器，返回值将是 10，因为 $4 \star 7 = 10$。 第一次询问要求计算 $1 \star 4 \star 7 \star 2$ 的值。如果使用样例评分器，由于 $$ 1 \star 4 \star 7 \star 2 = (1 \star (4 \star 7)) \star 2 = (1 \star 10) \star 2 = 11 \star 2 = 13 $$ 成立，因此过程 `Query` 应返回 13。 ### 约束条件 所有输入数据满足以下条件。 - $1 \leq N \leq 1000$。 - $0 \leq A_i \leq 1\,000\,000\,000$（$0 \leq i \leq N - 1$）。 - `Query` 的调用次数不超过 $10\,000$。 ### 评分细则 如果对于每个测试点，你的程序都能成功运行结束，未被判定为 **Wrong Answer [1]**，并且每次调用 `Query` 时都返回了正确的结果，那么你的程序将获得相应的分数。 分数的计算方式如下： (1) 如果对于每个测试点，都满足以下两个条件，则得分为 100： - 在 `Init` 中，调用 `Secret` 的次数小于等于 8000。 - 在每次调用 `Query` 的过程中，调用 `Secret` 的次数小于等于 1。 (2) 如果你的程序不满足 (1)，但满足以下两个条件，则得分为 30： - 在 `Init` 中，调用 `Secret` 的次数小于等于 8000。 - 在每次调用 `Query` 的过程中，调用 `Secret` 的次数小于等于 20。 (3) 如果你的程序不满足 (1) 或 (2)，则得分为 6。 翻译由 DeepSeek V3.2 完成