P11587 [KTSC 2022 R2] 编程测试

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include std::vector testset(std::vector A, std::vector B, std::vector L, std::vector U); ``` 题目译自 [2022년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2022/) T1「 [코딩 테스트 ](https://assets.ioikorea.kr/ioitst/2022/2/codingtest/codingtest_statement.pdf)」 注：原题时间限制为 2.5s，但是洛谷评测机不给力，因此放宽至 3s。

公司最近因为编程测试的流行，开始出一些编程测试题目并出售给 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 testset(vector A, vector B, vector L, vector 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$ 家企业的比赛的最大数量。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N\,M$ - 第 $2$ 行：$A[0]\,A[1]\,\cdots\,A[N-1]$ - 第 $3$ 行：$B[0]\,B[1]\,\cdots\,B[N-2]$ - 第 $4+j (0 \leq j \leq M-1)$ 行：$L[j]\,U[j]$

示例评测程序的输出格式如下： - 第 $1+j (0 \leq j \leq M-1)$ 行：$S[j]$

### 样例解释 #1 考虑 $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$|$0$|$1$|$1-\mathbf{2}$|$2-\mathbf{3}$| |比赛 $3$|$\mathbf{0 - 1}$|$\mathbf{1 - 2}$|$1-\mathbf{2}$|$2-\mathbf{3}$| 第 $1$ 家企业需要难度在 $1$ 级到 $2$ 级之间的题目。可以通过以下方式组成 $5$ 场比赛，使用了所有可能的题目，无法再组成更多的比赛。 | | $1$ 级 | $2$ 级 | | :----------: | :----------: | :----------: | |比赛 $1$|$1$|$2$| |比赛 $2$|$1$|$1-\mathbf{2}$| |比赛 $3$|$1$|$1 \mathbf{- 2}$| |比赛 $4$|$0-\mathbf{1}$|$\mathbf{2 - 3}$ |比赛 $5$|$\mathbf{1 - 2}$|$\mathbf{2 - 3}$| 因此，调用的 `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$ 详细子任务附加限制及分值如下表所示。 | Subtask | 分值 | 约束 | | :----------: | :----------: | :----------: | |$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$|$23$|无附加限制|