P12866 [JOI Open 2025] 抽奖 / Lottery

译自 [JOI Open 2025](https://contests.ioi-jp.org/open-2025/index.html) T2「[Lottery](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/lgmg41dn)」/ 「[くじ引き](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/ydv1gwqi)」。 **这是一道函数式交互题**。请使用 $\textcolor{red}{\texttt{C++\,20}}$ 提交。 **不要** $\texttt{\#include "lottery.h"}$。

JOI 君计划举办一场抽奖活动。活动将会用到偶数数量的袋子，一开始每袋中装着若干（可以是零个）红球和蓝球。玩家会一直来抽奖，直到有一个袋子被取空。每位玩家从每个袋子中各取一球，若取的红球数等于蓝球数，则中奖。取走的球不会放回袋中。 JOI 君准备了 $N$ 个袋子，编号 $0\sim N-1$。袋 $i$ 中装有 $X_i$ 个红球，$Y_i$ 个蓝球。 JOI 君会选择这 $N$ 个袋子中的若干个用在实际抽奖活动中。有 $Q$ 个计划，第 $j\, (1\le j\le Q)$ 个计划中，将会用到袋 $L_j,L_j+1,\ldots,R_j$。这里，保证 $R_j-L_j+1$ 是偶数。 为预订奖品，JOI 君想要知道每个计划中玩家最多可以中多少次奖。给定袋中球的数量和各个方案，试编程计算每个计划中玩家最多可以中多少次奖。 ### 实现细节 **这是一道函数式交互题**。你不应该，也不需要定义 `main` 函数。 **不要** $\texttt{\#include "lottery.h"}$。 你应当实现以下的函数： ```cpp void init(int N, int Q, std::vector X, std::vector Y); ``` - 该函数仅在开始时被调用一次。 - $\texttt{N}$ 指 JOI 君准备的袋子数 $N$。 - $\texttt{Q}$ 指计划数 $Q$。 - $\texttt{X}$ 是一个长度为 $N$ 的数组。$\texttt{X[i]}\, (0\le i\le N-1)$ 指袋 $i$ 中的红球数。 - $\texttt{Y}$ 是一个长度为 $N$ 的数组。$\texttt{Y[i]}\, (0\le i\le N-1)$ 指袋 $i$ 中的蓝球数。 ```cpp int max_prize(int L, int R) ``` - 该函数在 `init` 调用后被调用恰好 $Q$ 次。 - 第 $j\, (1\le j\le Q)$ 次调用： - $\texttt{L}$ 指第 $j$ 个计划的 $L_j$。 - $\texttt{R}$ 指第 $j$ 个计划的 $R_j$。 - 该函数必须返回第 $j$ 个计划中玩家最多可以中多少次奖。 ### 重要说明 - 你可以在程序中定义其他函数或使用全局变量。 - 你的程序不得使用标准输出输出，禁止以任何方式与任何文件交互。你可以输出调试信息到标准错误流。 ### 编译运行 你可以在「附件」中下载附件压缩包，压缩包中包含 Sample Grader 和本题的示例文件。 Sample Grader 是文件 $\texttt{grader.cpp}$。为测试程序，将 $\texttt{grader.cpp},\texttt{lottery.cpp},\texttt{lottery.h}$ 置于同一目录下，用以下命令来编译： ```bash g++ -std=gnu++20 -O2 -o grader grader.cpp lottery.cpp ``` 此外，你也可以运行压缩包中的 $\texttt{compile.sh}$ 来编译： ```bash ./complie.sh ``` 若编译成功，会生成名为 $\texttt{grader}$ 的可执行文件。 注意，实际测评时使用的 Grader 与 Sample Grader 不同。Sample Grader 以单进程方式执行，从标准输入流读入数据并将结果输出至标准输出流。

Sample Grader 从标准输入流读入以下格式的数据： > $N$ $Q$\ > $X_0$ $X_1$ $\cdots$ $X_{N-1}$\ > $Y_0$ $Y_1$ $\cdots$ $Y_{N-1}$\ > $L_1$ $R_1$\ > $L_2$ $R_2$\ > $\vdots$\ > $L_Q$ $R_Q$

Sample Grader 将每次 `max_prize` 的调用结果输出至标准输出流。

### 样例解释 #### 样例 $1$ 解释 | 调用函数 | 返回值 | | - | - | | $\texttt{init(5,3,[2,1,3,1,0],[1,1,0,2,0])}$ | | | $\texttt{max\_prize(0,3)}$ | $2$ | | $\texttt{max\_prize(1,4)}$ | $0$ | | $\texttt{max\_prize(2,3)}$ | $2$ | **第一次调用** `max_prize` 时，使用了袋 $0,1,2,3$。按照以下方式取球，中奖次数为 $2$： - 第一位玩家从袋 $0,1,2,3$ 中依次取出红球、蓝球、红球、蓝球。由于红蓝球数量相等，该玩家中奖。 - 第二位玩家从袋 $0,1,2,3$ 中依次取出蓝球、红球、红球、蓝球。由于红蓝球数量相等，该玩家中奖。 - 袋 $1$ 被取空，抽奖活动结束。 无法得到 $\gt 2$ 次的中奖次数，所以第一次调用返回 $2$。 **第二次调用** `max_prize` 时，使用了袋 $1,2,3,4$。由于袋 $4$ 是空的，没人抽奖抽奖活动就结束了。因此，无人中奖，第二次调用返回 $0$。 **第三次调用** `max_prize` 时，使用了袋 $2,3$。按照以下方式取球，中奖次数为 $3$： - 第一位玩家从袋 $2,3$ 中依次取出红球、红球。没有中奖。 - 第二位玩家从袋 $2,3$ 中依次取出红球、蓝球。由于红蓝球数量相等，该玩家中奖。 - 第三位玩家从袋 $2,3$ 中依次取出红球、蓝球。由于红蓝球数量相等，该玩家中奖。 - 袋 $2,3$ 被取空，抽奖活动结束。 无法得到 $\gt 2$ 次的中奖次数，所以第三次调用返回 $2$。 样例 $1$ 满足子任务 $1,2,4\sim 6$ 的限制。 #### 样例 $2$ 解释 | 调用函数 | 返回值 | | - | - | | $\texttt{init(6,5,[1,3,3,2,1,0],[1,2,1,1,2,1])}$ | | | $\texttt{max\_prize(0,1)}$ | $2$ | | $\texttt{max\_prize(1,2)}$ | $3$ | | $\texttt{max\_prize(1,4)}$ | $3$ | | $\texttt{max\_prize(2,5)}$ | $1$ | | $\texttt{max\_prize(4,5)}$ | $1$ | 样例 $2$ 满足所有子任务的限制。 ### 数据范围 - $2\le N\le 200\, 000$； - $1\le Q\le 500\, 000$； - $0\le X_i\le 10^9\, (0\le i\le N-1)$； - $0\le Y_i\le 10^9\, (0\le i\le N-1)$； - $0\le L_j\lt R_j\le N-1\, (1\le j\le Q)$； - $R_j-L_j+1$ 为偶数 $(1\le j\le Q)$； - 输入的值都是整数。 ### 子任务 - $\text{Subtask 1 (16 pts)}$：$Q,X_i,Y_i,R_j-L_j+1\le 100\, (0\le i\le N-1,1\le j\le Q)$； - $\text{Subtask 2 (16 pts)}$：$Q,R_j-L_j+1\le 100\, (1\le j\le Q)$ - $\text{Subtask 3 (19 pts)}$：$Q\le 200\, 000$，$L_j\le L_{j+1},R_j\le R_{j+1}\, (1\le j\le Q-1)$ - $\text{Subtask 4 (12 pts)}$：$N\le 20\, 000$，$Q\le 50\, 000$； - $\text{Subtask 5 (14 pts)}$：$N\le 100\, 000$，$Q\le 200\, 000$； - $\text{Subtask 6 (23 pts)}$：无额外限制。