---

注意事项

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

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

请在提交源代码前添加 #include "codingtest.h"。

---

题目描述

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1 「김경근」

公司最近因为编程测试的流行，开始出一些编程测试题目并出售给 IT 公司。

为了方便，公司将题目的难度分为 $0$ 到 $N-1$ 个等级。目前，公司有 $A[i]$ 个难度为 $i$ 级的题目，还有 $B[i]$ 个难度不确定是 $i$ 级还是 $i+1$ 级的题目。除此之外，没有其他难度的题目。

公司正在寻找愿意购买题目的企业。目前有 $M$ 家企业表示有购买意向，编号从 $0$ 到 $M-1$。第 $j$ $(0 \leq j \leq M-1)$ 家企业只对难度在 $L[j]$ 级到 $U[j]$ 级之间的题目感兴趣。

公司计划将难度在 $L[j]$ 级到 $U[j]$ 级之间的题目按难度各选一个，组成一套题出售给第 $j$ 家企业，我们称之为一场比赛。如果只向第 $j$ 家企业出售题目，最多可以出售多少场比赛？对于难度不确定是 $i$ 级还是 $i+1$ 级的题目，需要适当分配难度，使得出售的比赛数量最多，并且每场比赛中的题目不能重复使用。

---

实现细节

你需要实现以下函数：

vector<int> testset(vector<int> A, vector<int> B, vector<int> L, vector<int> U);

• 该函数只会被调用一次。
• A：长度为 $N$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-1)$，$A[i]$ 是难度为 $i$ 级的题目数量。
• B：长度为 $N-1$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-2)$，$B[i]$ 是难度不确定是 $i$ 级还是 $i+1$ 级的题目数量。
• L, U：长度为 $M$ 的整数数组。对于每个 $j$ $(0 \leq j \leq M-1)$，$L[j], U[j]$ 分别是第 $j$ 家企业感兴趣的题目的最小难度和最大难度。
• 该函数返回一个长度为 $M$ 的整数数组 $S$。对于每个 $j$ $(0 \leq j \leq M-1)$，$S[j]$ 是可以出售给第 $j$ 家企业的比赛的最大数量。

注意，提交的代码中不应包含任何输入输出操作。

---

样例

考虑 $N=4$, $M=2$, $A=[2,3,1,1]$, $B=[1,3,2]$, $L=[0,1]$, $U=[3,2]$ 的情况。

评测程序将调用如下函数：

testset({2, 3, 1, 1}, {1, 3, 2}, {0, 1}, {3, 2});

• 第 $0$ 家企业需要难度在 $0$ 级到 $3$ 级之间的题目。可以通过以下方式组成 $3$ 场比赛，剩下一个难度为 $1$ 级的题目，无法再组成更多场比赛。

比赛	0 级	1 级	2 级	3 级
1	0	1	2	3
2			$1-\mathbf{2}$	$2-\mathbf{3}$
3	$\mathbf{0 - 1}$	$\mathbf{1 - 2}$

• 第 $1$ 家企业需要难度在 $1$ 级到 $2$ 级之间的题目。可以通过以下方式组成 $5$ 场比赛，使用了所有可能的题目，无法再组成更多的比赛。

比赛	1 级	2 级
1	1	2
2		$1-\mathbf{2}$
3
4	$0-\mathbf{1}$	$\mathbf{2 - 3}$
5	$\mathbf{1 - 2}$

因此，调用的 testset 函数应返回 $S=[3, 5]$。

---

数据范围与提示

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

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• 对于所有 $i$ $(0 \leq i \leq N-1)$，$0 \leq A[i] \leq 10^{8}$
• 对于所有 $i$ $(0 \leq i \leq N-2)$，$0 \leq B[i] \leq 10^{8}$
• 对于所有 $i$ $(0 \leq j \leq M-1)$，$0 \leq L[i] \leq U[i] \leq N-1$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	3	$A[i] \leq 1000$ $(0 \leq i \leq N-1)$； $B[i] \leq 1000$ $(0 \leq i \leq N-2)$； $U[j]-L[j] \leq 2$ $(0 \leq j \leq M-1)$
2	15	$M \leq 100$
3	36	$N \leq 5000$
4	23	对于所有 $j$ $(0 \leq j \leq M-1)$，$L[j]=0$
5		无附加限制

---

示例评测程序

示例评测程序按以下格式读取输入：

第 1 行：N M
第 2 行：A[0] A[1] ... A[N-1]
第 3 行：B[0] B[1] ... B[N-2]
第 4+j (0 ≤ j ≤ M-1) 行：L[j] U[j]

示例评测程序的输出格式如下：

第 1+j (0 ≤ j ≤ M-1) 行：S[j]

---