题目背景

译自 JOI Open 2025 T2「Lottery」/ 「くじ引き」。

这是一道函数式交互题。请使用 $\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"}$。

你应当实现以下的函数：

void init(int N, int Q, std::vector<int> X, std::vector<int> 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$ 中的蓝球数。

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}$ 置于同一目录下，用以下命令来编译：

g++ -std=gnu++20 -O2 -o grader grader.cpp lottery.cpp

此外，你也可以运行压缩包中的 $\texttt{compile.sh}$ 来编译：

./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 的调用结果输出至标准输出流。

5 3
2 1 3 1 0
1 1 0 2 0
0 3
1 4
2 3

2
0
2

6 5
1 3 3 2 1 0
1 2 1 1 2 1
0 1
1 2
1 4
2 5
4 5

2
3
3
1
1

提示

样例解释

样例 $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)}$
$\texttt{max\_prize(2,5)}$	$1$
$\texttt{max\_prize(4,5)}$

样例 $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)}$：无额外限制。