分数: 525 点
问题陈述
高桥计划参加 N AtCoder 竞赛。
在 i第届比赛(1 \leq i \leq N),如果他的评分介于 L_i 和 R_i (含),他的评分增加 1.
你被给予 Q 按以下格式查询:
- 一个整数 给出了 X 。假设高桥的初始评级是 X,参加全部后确定他的评分 N 比赛。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq 5 \times 10^5 (1 \leq i \leq N)
- 1 \leq Q \leq 3 \times 10^5
- 对于每个查询, 1 \leq X \leq 5 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
在这里, \text{query}_i 是 i-第一个查询,格式为:
X
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
5 1 5 1 3 3 6 2 4 4 7 3 3 2 5
示例输出 1
6 6 8
对于第一个查询,评级更改如下:
- 在第一场比赛中,评分介于 1 和 5,所以它增加了 1,成为 4.
- 在第二次比赛中,评分不介于 1 和 3,所以它仍然是 4.
- 在第三次比赛中,评分介于 3 和 6,所以它增加了 1,成为 5.
- 在第四次比赛中,评分不介于 2 和 4,所以它仍然是 5.
- 在第五届比赛中,评分介于 4 和 7,所以它增加了 1,成为 6.
对于第二个查询,第 1、2、3 和 5 次比赛中的评分增加,结束于 6.
对于第 3 个查询,第 1、第 3 和第 5 场比赛的评分增加,结束于 8.
示例输入 2
10 1 1999 1 1999 1200 2399 1 1999 1 1999 1 1999 2000 500000 1 1999 1 1999 1600 2799 7 1 1995 2000 2399 500000 2799 1000
示例输出 2
8 2002 2003 2402 500001 2800 1007
示例输入 3
15 260522 414575 436426 479445 148772 190081 190629 433447 47202 203497 394325 407775 304784 463982 302156 468417 131932 235902 78537 395728 223857 330739 286918 329211 39679 238506 63340 186568 160016 361868 10 287940 296263 224593 101449 336991 390310 323355 177068 11431 8580
示例输出 3
287946 296269 224599 101453 336997 390315 323363 177075 11431 8580