AT_joi2026final_j パン職人 (Baker)

JOI Bakery 是一家以其美味可颂而闻名的面包店。JOI Bakery 有 $N$ 位烘焙师，编号从 $1$ 到 $N$。第 $i$ 位烘焙师（$1 \leq i \leq N$）制作一只可颂需耗时 $i$ 分钟。每位烘焙师在同一时间只能制作一只可颂。 今天，将有 $M$ 位顾客（编号 $1$ 到 $M$）计划依次到 JOI Bakery，每位顾客都准备点一只可颂。第 $j$ 位顾客（$1 \leq j \leq M$）将在第 $T_j$ 分钟时下单，这里的“时间 $t$”表示从现在起过了 $t$ 分钟。然而，如果顾客不能在下单后 $L$ 分钟内拿到可颂，他（她）将失望离开。也就是说，为了完成第 $j$ 位顾客（$1 \leq j \leq M$）的订单，必须在 $T_j + L$ 分钟（可以正好在 $T_j + L$ 分钟）内完成。 面包店经理 K 今天只打算让一名烘焙师工作，并在考虑应派哪位烘焙师、何时让其上岗。由于烘焙师在工作时精神非常集中，**他们不会理会上岗时间之后的新订单（不包括正好在上岗时间下的订单）**。即，如果某烘焙师在时间 $t$ 开始上岗，则不能完成 $T_j > t$ 的顾客订单。 经理 K 正在考虑 $Q$ 套方案。第 $q$ 套方案（$1 \leq q \leq Q$）是指让第 $A_q$ 位烘焙师在时间 $B_q$ 上岗。为方便决策，对于每套方案，他想知道若按此执行，最多能完成多少位顾客的订单。请注意，烘焙师到岗后开始制作可颂的时间，以及完成上一只可颂后开始下一个的间隔，可以忽略不计。 请你根据顾客来店信息与工作安排，为每套方案计算最多能完成多少人的订单。 ---

从标准输入中读取数据。 > $N\ M\ L\ Q$ > $T_1\ T_2\ \cdots\ T_M$ > $A_1\ B_1$ > $A_2\ B_2$ > $\vdots$ > $A_Q\ B_Q$

输出 $Q$ 行。第 $q$ 行（$1 \leq q \leq Q$）为在第 $q$ 套方案下最多可以完成的顾客订单数。 ---

### 子任务 1. （$8$ 分）$M \leq 10$，$Q \leq 100\,000$。 2. （$12$ 分）$M \leq 500$，$Q \leq 100\,000$。 3. （$30$ 分）$T_M \leq B_q < T_1 + L$（$1 \leq q \leq Q$）。 4. （$10$ 分）$T_M \leq B_q$（$1 \leq q \leq Q$）。 5. （$22$ 分）$M \leq 500\,000$，$Q \leq 100\,000$。 6. （$18$ 分）无额外约束。 --- ### 样例说明 1 对于第 1 套方案：第 2 号烘焙师在第 3 分钟上岗，可以完成顾客 1、2、3 的订单，具体如下： - 首先，从第 3 分钟开始制作顾客 1 的可颂，2 分钟后（第 5 分钟）完成。（满足需在 $T_1 + L = 0 + 6 = 6$ 分钟前完成。） - 接着，从第 5 分钟开始制作顾客 2 的可颂，2 分钟后（第 7 分钟）完成。（满足 $T_2 + L = 2 + 6 = 8$ 分钟前完成。） - 之后，从第 7 分钟开始制作顾客 3 的可颂，2 分钟后（第 9 分钟）完成。（满足 $T_3 + L = 3 + 6 = 9$ 分钟前完成。） 顾客 4 的订单因其下单时间在烘焙师上岗时间之后，不被处理。因此，最多可完成 3 位顾客的订单，第 1 行输出 3。 对于第 2 套方案：第 1 号烘焙师在第 6 分钟上岗，可顺序完成顾客 3 与 2 的订单。例如： - 首先，从第 6 分钟开始制作顾客 3 的可颂，1 分钟后（第 7 分钟）完成。（满足 $T_3 + L = 3 + 6 = 9$ 分钟前完成。） - 接着，从第 7 分钟开始制作顾客 2 的可颂，1 分钟后（第 8 分钟）完成。（满足 $T_2 + L = 2 + 6 = 8$ 分钟前完成。） 顾客 4 的订单被忽略，因为下单时间在上岗后。此外，顾客 1 的订单需在第 6 分钟前完成，无法完成。因此，第 2 行输出 2。 对于第 3 套方案：第 3 号烘焙师在第 3 分钟上岗，可完成顾客 1、3 或顾客 2、3 的订单，但无法全部完成 1、2、3 号顾客的订单，且也无法完成顾客 4 的订单，因此答案为 2。 对于第 4 套方案：第 4 号烘焙师在第 7 分钟上岗，无法完成任何订单，因此输出 0。 该组样例满足子任务 $1, 2, 5, 6$ 的数据范围。 --- ### 样例说明 2 此组样例满足所有子任务的数据范围。 --- ### 样例说明 3 此组样例满足子任务 $1, 2, 5, 6$ 的数据范围。 ### 数据范围 - $1 \leq N \leq 4\times 10^{12}$。 - $1 \leq M \leq 2\,000\,000$。 - $1 \leq L \leq 2\times 10^{12}$。 - $1 \leq Q \leq 400\,000$。 - $0 \leq T_j \leq 2\times 10^{12}$（$1 \leq j \leq M$）。 - $T_j \leq T_{j+1}$（$1 \leq j \leq M-1$）。 - $1 \leq A_q \leq N$（$1 \leq q \leq Q$）。 - $0 \leq B_q \leq 4\times 10^{12}$（$1 \leq q \leq Q$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译