← 返回题目列表

AtCoder · past202012_n

N. 旅行社

中文机器翻译题面 查看原题

分数: 6 点

警告

2020 年 12 月 27 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

在一个国家,有 N 城市,编号 1 通过 N.
国家有 N - 1 道路,充满危险。因此,每条路都只允许年龄在一定范围内的人通行;的 i第条路连接城市 i 和城市 i + 1 双向,并且仅限年龄介于 L_i 和 R_i 可以遍历它。
您已在这个国家/地区创办了一家旅行社。回应 Q 来自客户的询问。
在 i第一个查询,给定值 A_i 和 B_i,查找某个城市的数量 A_i岁的人可以从城市开始到达 B_i 和穿越道路。 (城市 B_i 也被认为是可达的。)我们假设此人在旅途中不会变老。

约束

  • 1 \le N \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le L_i \le R_i \le 10^9
  • 1 \le A_i \le 10^9
  • 1 \le B_i \le N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
L_1 R_1
L_2 R_2
L_3 R_3
\hspace{15pt} \vdots
L_{N - 1} R_{N - 1}
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_Q B_Q

输出

打印 Q 行。的 i- 第行应包含对 i-第一个查询。


示例输入 1

4 3
3 6
2 5
1 2
3 1
2 2
1 4

示例输出 1

3
3
2

在第一个查询中, 3岁从城市开始 1。除以下道路外 3-rd 一个还可以,所以这个人可以到达三个城市: City 1 通过 3.
在第二个查询中, 2岁从城市开始 2。除以下道路外 1-st 一个是可以通过的,所以这个人可以到达三个城市: City 2 通过 4.
在第三个查询中, 1岁从城市开始 4。只有第三条路可以通行,所以这个人可以到达两个城市: 城市 3 和 4.


示例输入 2

6 3
4 7
3 8
1 6
5 9
7 10
5 1
7 6
4 6

示例输出 2

5
3
1