#P14174. [JOI Open 2025] 抽奖 / Lottery

    ID: 13380 传统题 5000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400数学二分线段树可持久化背包DP

[JOI Open 2025] 抽奖 / Lottery

[JOI Open 2025] 抽奖 / Lottery

题目描述

JOI 君计划举办一场抽奖活动。活动将会用到偶数数量的袋子,一开始每袋中装着若干(可以是零个)红球和蓝球。玩家会一直来抽奖,直到有一个袋子被取空。每位玩家从每个袋子中各取一球,若取的红球数等于蓝球数,则中奖。取走的球不会放回袋中。

JOI 君准备了 NN 个袋子,编号 0∼N−10\sim N-1。袋 ii 中装有 XiX_i 个红球,YiY_i 个蓝球。

JOI 君会选择这 NN 个袋子中的若干个用在实际抽奖活动中。有 QQ 个计划,第 j (1≤j≤Q)j\, (1\le j\le Q) 个计划中,将会用到袋 Lj,Lj+1,…,RjL_j,L_j+1,\ldots,R_j。这里,保证 Rj−Lj+1R_j-L_j+1 是偶数。

为预订奖品,JOI 君想要知道每个计划中玩家最多可以中多少次奖。给定袋中球的数量和各个方案,试编程计算每个计划中玩家最多可以中多少次奖。

实现细节

本题是函数式题目。请选择 C++20,提交包含 #include "lottery.h" 的一份源代码。Hydro 将提供评测头文件与程序入口。你需要实现以下两个函数。

void init(int N, int Q, std::vector<int> X, std::vector<int> Y);
  • 该函数仅在开始时被调用一次。
  • N\texttt{N} 指 JOI 君准备的袋子数 NN。
  • Q\texttt{Q} 指计划数 QQ。
  • X\texttt{X} 是一个长度为 NN 的数组。X[i] (0≤i≤N−1)\texttt{X[i]}\, (0\le i\le N-1) 指袋 ii 中的红球数。
  • Y\texttt{Y} 是一个长度为 NN 的数组。Y[i] (0≤i≤N−1)\texttt{Y[i]}\, (0\le i\le N-1) 指袋 ii 中的蓝球数。
int max_prize(int L, int R);
  • 该函数在 init 调用后被调用恰好 QQ 次。
  • 第 j (1≤j≤Q)j\, (1\le j\le Q) 次调用:
    • L\texttt{L} 指第 jj 个计划的 LjL_j。
    • R\texttt{R} 指第 jj 个计划的 RjR_j。
    • 该函数必须返回第 jj 个计划中玩家最多可以中多少次奖。

重要说明

  • 你可以在程序中定义其他函数或使用全局变量。
  • 你的程序不得使用标准输入、标准输出或访问文件。你可以输出调试信息到标准错误流。

本地测试

下载 官方样例评测包。将自己的源文件保存为 lottery.cpp,与 grader.cpp、lottery.h 放在同一目录,然后编译和运行。

g++ -std=gnu++20 -O2 -o grader grader.cpp lottery.cpp
./grader < sample-01-in.txt

输入格式

Sample Grader 从标准输入流读入以下格式的数据:

NN QQ
X0X_0 X1X_1 ⋯\cdots XN−1X_{N-1}
Y0Y_0 Y1Y_1 ⋯\cdots YN−1Y_{N-1}
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LQL_Q RQR_Q

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

2
0
2

输入输出样例 #2

输入 #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

2
3
3
1
1

说明/提示

样例解释

样例 11 解释

调用函数 返回值
init(5,3,[2,1,3,1,0],[1,1,0,2,0])\texttt{init(5,3,[2,1,3,1,0],[1,1,0,2,0])}
max_prize(0,3)\texttt{max\_prize(0,3)} 22
max_prize(1,4)\texttt{max\_prize(1,4)} 00
max_prize(2,3)\texttt{max\_prize(2,3)} 22

第一次调用 max_prize 时,使用了袋 0,1,2,30,1,2,3。按照以下方式取球,中奖次数为 22:

  • 第一位玩家从袋 0,1,2,30,1,2,3 中依次取出红球、蓝球、红球、蓝球。由于红蓝球数量相等,该玩家中奖。
  • 第二位玩家从袋 0,1,2,30,1,2,3 中依次取出蓝球、红球、红球、蓝球。由于红蓝球数量相等,该玩家中奖。
  • 袋 11 被取空,抽奖活动结束。

无法得到 >2\gt 2 次的中奖次数,所以第一次调用返回 22。

第二次调用 max_prize 时,使用了袋 1,2,3,41,2,3,4。由于袋 44 是空的,抽奖活动立即结束。因此,无人中奖,第二次调用返回 00。

第三次调用 max_prize 时,使用了袋 2,32,3。按照以下方式取球,中奖次数为 22:

  • 第一位玩家从袋 2,32,3 中依次取出红球、红球。没有中奖。
  • 第二位玩家从袋 2,32,3 中依次取出红球、蓝球。由于红蓝球数量相等,该玩家中奖。
  • 第三位玩家从袋 2,32,3 中依次取出红球、蓝球。由于红蓝球数量相等,该玩家中奖。
  • 袋 2,32,3 被取空,抽奖活动结束。

无法得到 >2\gt 2 次的中奖次数,所以第三次调用返回 22。

样例 11 满足子任务 1,2,4∼61,2,4\sim 6 的限制。

样例 22 解释

调用函数 返回值
init(6,5,[1,3,3,2,1,0],[1,2,1,1,2,1])\texttt{init(6,5,[1,3,3,2,1,0],[1,2,1,1,2,1])}
max_prize(0,1)\texttt{max\_prize(0,1)} 22
max_prize(1,2)\texttt{max\_prize(1,2)} 33
max_prize(1,4)\texttt{max\_prize(1,4)}
max_prize(2,5)\texttt{max\_prize(2,5)} 11
max_prize(4,5)\texttt{max\_prize(4,5)}

样例 22 满足所有子任务的限制。

数据范围

  • 2≤N≤200 0002\le N\le 200\, 000;
  • 1≤Q≤500 0001\le Q\le 500\, 000;
  • 0≤Xi≤109 (0≤i≤N−1)0\le X_i\le 10^9\, (0\le i\le N-1);
  • 0≤Yi≤109 (0≤i≤N−1)0\le Y_i\le 10^9\, (0\le i\le N-1);
  • 0≤Lj<Rj≤N−1 (1≤j≤Q)0\le L_j\lt R_j\le N-1\, (1\le j\le Q);
  • Rj−Lj+1R_j-L_j+1 为偶数 (1≤j≤Q)(1\le j\le Q);
  • 输入的值都是整数。

子任务

每个子任务内的测试点全部通过后,获得该子任务的分数。

  • Subtask 1 (16 pts)\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)$;
  • Subtask 2 (16 pts)\text{Subtask 2 (16 pts)}:Q,Rj−Lj+1≤100 (1≤j≤Q)Q,R_j-L_j+1\le 100\, (1\le j\le Q)
  • Subtask 3 (19 pts)\text{Subtask 3 (19 pts)}:Q≤200 000Q\le 200\, 000,Lj≤Lj+1,Rj≤Rj+1 (1≤j≤Q−1)L_j\le L_{j+1},R_j\le R_{j+1}\, (1\le j\le Q-1)
  • Subtask 4 (12 pts)\text{Subtask 4 (12 pts)}:N≤20 000N\le 20\, 000,Q≤50 000Q\le 50\, 000;
  • Subtask 5 (14 pts)\text{Subtask 5 (14 pts)}:N≤100 000N\le 100\, 000,Q≤200 000Q\le 200\, 000;
  • Subtask 6 (23 pts)\text{Subtask 6 (23 pts)}:无额外限制。