注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 11 及以上）

题目描述

译自 JOI Open 2014 Day2 T3「秘密 / Secret」

Anna 发明了一个秘密的二元运算 $\star$。对于不超过 $10^9$ 的非负整数 $x, y$，会得到一个固定的不超过 $10^9$ 的非负整数 $x \star y$。这个运算 $\star$ 是满足结合律的。也就是说，对于不超过 $10^9$ 的非负整数 $x, y, z$，有等式 $(x \star y) \star z=x \star(y \star z)$ 成立。这个值简单地用 $x \star y \star z$ 表示。

Anna 计划和 Bruno 玩一个游戏。她让他猜测运算 $\star$。她给他展示了 $N$ 个整数 $A_{0}, A_{1}, \ldots, A_{N-1}$。她会给出一些这样的查询：「$A_{L} \star A_{L+1} \star \cdots \star A_{R}$ 的值是多少？」

Bruno 觉得没有提示的话这个游戏会很困难。Anna 决定给他一些提示。对于每个提示，Bruno 可以选择 $x, y$，Anna 就会告诉他 $x \star y$ 的值。他可以在游戏开始时，即当给出整数 $A_{0}, A_{1}, \ldots, A_{N-1}$ 时，询问提示。他也可以在她给出一个查询时，询问提示。当然，他想减少询问提示的次数。因为他想表现得像他对运算 $\star$ 几乎什么都知道，他特别想减少在给出查询后询问提示的次数。

编写一个程序，实现 Bruno 询问提示和正确回答 Anna 的查询的策略。

实现细节

你需要在程序中包含 secret.h 头文件。

你的程序应该实现以下函数。

• $\texttt{void Init(int N, int A[])}$

  这个函数只在开始时被调用一次。

  • 参数 $\texttt{N}$ 是 Anna 展示的整数的个数 $N$。
  • 参数 $\texttt{A}$ 是一个长度为 $N$ 的数组。元素 $\texttt{A}[0], \texttt{A}[1], \ldots, \texttt{A}[\texttt{N}-1]$ 是她展示的整数 $A_{0}, A_{1}, \ldots, A_{N-1}$。

• $\texttt{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}$ 的值。

以下函数可以在你的程序中被调用。

• $\texttt{int Secret(int X, int Y)}$

  这个函数在 Bruno 询问一个提示时被调用。这意味着他在询问 $X \star Y$ 的值。

  • 参数 $\texttt{X}$ 和 $\texttt{Y}$ 应满足 $0 \leq X,Y \leq 10^9$。如果条件不满足，你的程序会被判为 Wrong Answer [1]。
  • 这个函数返回 $X \star Y$ 的值。

编译和测试运行

你可以从「文件」页面下载样例交互器并测试你的程序。「文件」页面也包含一个样例源文件。

样例交互器是文件 grader.cpp。为了测试你的程序，你需要将 grader.cpp，secret.cpp 和 secret.h 三个文件放在同一文件夹下，并运行如下命令编译你的程序。

g++ -02 -std=c++11 -o grader grader.cpp secret.cpp

当编译成功后，会产生一个可执行文件 grader。

请注意实际的交互器和样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入，并输出结果到标准输出。

样例评测器的说明

样例评测器假设 $x \star y=\min \left\{x+2\left\lfloor\frac{y}{2}\right\rfloor, 10^9\right\}$。这里 $\lfloor r\rfloor$ 表示不大于 $r$ 的最大整数。注意，这与实际评测器的运算不同。

样例交互器输入

样例评测器从标准输入读取以下内容。

第一行包含一个整数 $N$，表示 Anna 展示的整数的个数。

第二行包含用空格分隔的整数 $A_{0}, A_{1}, \ldots, 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)$，表示 Anna 查询 $A_{L_{j}} \star A_{L_{j}+1} \star \cdots \star A_{R_{j}}$ 的值。

样例交互器输出

样例交互器输出如下信息到标准输出。

• 如果你的程序被判为正确，它会输出在函数 $\texttt{Init}$ 中调用 $\texttt{Secret}$ 的次数，以及在每次调用函数 $\texttt{Query}$ 中调用 $\texttt{Secret}$ 的最大次数。
• 如果你的程序被判为错误，它将输出错误类别，如 Wrong Answer [1]。

计分

如果你的程序对每个测试用例都成功终止，没有被认为是 Wrong Answer [1]，并且对每次调用 $\texttt{Query}$ 都返回正确的值，你的分数将按如下方式计算：

• 如果你的程序对每个测试点都满足以下两个条件，你的分数是 $100$：
  • 在 $\texttt{Init}$ 中，调用 $\texttt{Secret}$ 的次数小于等于 $8000$。
  • 在每次调用 $\texttt{Query}$ 中，调用 $\texttt{Secret}$ 的次数小于等于 $1$。
• 如果你的程序不满足上述条件并且满足以下两个条件，你的分数是 $30$：
  • 在 $\texttt{Init}$ 中，调用 $\texttt{Secret}$ 的次数小于等于 $8000$。
  • 在每次调用 $\texttt{Query}$ 中，调用 $\texttt{Secret}$ 的次数小于等于 $20$。
• 如果你的程序不满足上述任何一条，你的分数是 $6$。

8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4

这是一个样例评测器的输入和函数之间交互的例子。如果使用样例评测器，返回值如下。

函数调用	返回值
$\texttt{Init(8,[1,4,7,2,5,8,3,6])}$
$\texttt{Query(0,3)}$	$13$
$\texttt{Query(1,7)}$	$32$
$\texttt{Query(5,5)}$	$8$
$\texttt{Query(2,4)}$	$13$

函数 $\texttt{Secret}$ 可以在函数 $\texttt{Init}$ 或函数 $\texttt{Query}$ 中被调用。如果使用样例评测器时，$4 \star 7=10$。所以当调用 $\texttt{Secret(4,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$$

所以函数 $\texttt{Query}$ 应该返回 $13$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 1000$
• $0 \leq A_{i} \leq 10^9\ (0 \leq i \leq N-1)$
• 调用 $\texttt{Query}$ 的次数小于等于 $10000$