AT_joig2024_f.感染シミュレーション (Infection Simulation)

EGOI 食堂昨天迎来了 $N$ 名顾客。每位顾客都被分配了 $1$ 到 $N$ 的编号，其中第 $i$ 位顾客（$1 \leq i \leq N$）的进店时间为 $L_i$，离店时间为 $R_i$。如今已知，其中有一位顾客在到店时已感染了目前在 JOI 国流行的新型传染病 X。

传染病 X 的传染难度以整数 $x$ 表示。具体而言，对每位顾客 $i$（$1 \leq i \leq N$），如果其与至少一名感染者同时在食堂内的累计时间达到 $x$，那么他就会成为新的感染者。

由于 JOI 国采取了严格的防疫政策，必须精确掌握感染者人数。但令人头疼的是，具体是哪位顾客在进店时感染了感染症 X 不明，传染难度 $x$ 也不清楚。

因此，EGOI 食堂的店长理惠决定针对 $Q$ 个场景，分别计算最终有多少人被感染。第 $j$ 个场景（$1 \leq j \leq Q$）里，编号为 $P_j$ 的顾客是唯一最初的感染者，且传染病 X 的传染难度为 $X_j$。

给定顾客和各个场景的信息，请编写程序，输出每个场景下最终被感染顾客的人数。注意，如果某人正好在离店时刻感染，也计入感染人数。同时，已感染的顾客不会变回未感染者。

输入格式如下：

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$…$
$L_N$ $R_N$
$Q$
$P_1$ $X_1$
$P_2$ $X_2$
$…$
$P_Q$ $X_Q$

输出 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）输出第 $j$ 个场景下最终被感染顾客的人数。

子任务

1. （2 分）$L_i = 0$（$1 \leq i \leq N$），$R_i = 10$（$1 \leq i \leq N$），$Q \leq 5$。
2. （3 分）$L_i = 0$（$1 \leq i \leq N$），$Q \leq 5$。
3. （6 分）$L_i = 0$（$1 \leq i \leq N$）。
4. （10 分）$N \leq 500$，$Q \leq 5$，$R_i \leq 500$（$1 \leq i \leq N$），$X_j \leq 500$（$1 \leq j \leq Q$）。
5. （11 分）$N \leq 500$，$Q \leq 5$。
6. （16 分）$Q \leq 5$。
7. （13 分）$P_j = 1$（$1 \leq j \leq Q$），$L_1 < L_2 < … < L_N$，$R_1 < R_2 < … < R_N$。
8. （14 分）$P_j = 1$（$1 \leq j \leq Q$）。
9. （15 分）$\min_{1 \leq i \leq N}(R_i - L_i)$ 不小于 $\max_{1 \leq j \leq Q}(X_j)$。
10. （10 分）无额外限制。

样例说明 1

在第 $1$ 个场景中，最初的感染者是顾客 $1$，传染病 X 的传染难度为 $15$，感染传播过程如下：

• 时刻 $10$，顾客 $1$ 进店。
• 时刻 $20$，顾客 $2$ 进店。
• 时刻 $35$，顾客 $2$ 与至少一名感染者在食堂共处的累计时间达到 $15$，顾客 $2$ 被感染。
• 时刻 $40$，顾客 $1$ 离店。
• 时刻 $45$，顾客 $3$ 进店。
• 时刻 $60$，顾客 $3$ 与至少一名感染者在食堂共处的累计时间达到 $15$，顾客 $3$ 被感染，与此同时顾客 $3$ 离店。
• 时刻 $70$，顾客 $4$ 进店。
• 时刻 $80$，顾客 $2$ 离店。
• 时刻 $95$，顾客 $4$ 离店。顾客 $4$ 与至少一名感染者共处总计 $10$ 单位时间，未达到传染难度 $15$，未被感染。

最终，顾客 $1, 2, 3$ 共 $3$ 人被感染，因此第 $1$ 行输出 $3$。

此输入满足子任务 $4, 5, 6, 8, 9, 10$ 的限制。

样例说明 2

在第 $1$ 个场景下，最终顾客 $1, 2, 3, 4, 6, 7, 8$ 共 $7$ 人感染，因此第 $1$ 行输出 $7$。
在第 $2$ 个场景中，最终仅有顾客 $1$ 感染，因此第 $2$ 行输出 $1$。
在第 $3$ 个场景中，最终顾客 $2, 3, 4, 7, 8$ 共 $5$ 人感染，因此第 $3$ 行输出 $5$。

此输入满足子任务 $2, 3, 4, 5, 6, 10$ 的限制。

样例说明 3

此输入满足子任务 $1, 2, 3, 5, 6, 8, 10$ 的限制。

样例说明 4

此输入满足子任务 $4, 5, 6, 9, 10$ 的限制。

样例说明 5

此输入满足子任务 $4, 5, 6, 7, 8, 9, 10$ 的限制。

样例说明 6

此输入满足子任务 $4, 5, 6, 8, 10$ 的限制。

样例说明 7

此输入满足子任务 $4, 5, 6, 9, 10$ 的限制。

数据范围

• $1 \leq N \leq 100\,000$。
• $0 \leq L_i < R_i \leq 10^9$（$1 \leq i \leq N$）。
• $1 \leq Q \leq 100\,000$。
• $1 \leq P_j \leq N$（$1 \leq j \leq Q$）。
• $1 \leq X_j \leq 10^9$（$1 \leq j \leq Q$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译