N - Travel Agency Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

ある国には 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

1 個目の質問では、3 才の人が都市 1 から旅行を始めます。3 番目の道路以外は通れるので、到達可能なのは都市 1 から都市 3 までの 3 個です。
2 個目の質問では、2 才の人が都市 2 から旅行を始めます。1 番目の道路以外は通れるので、到達可能なのは都市 2 から都市 4 までの 3 個です。
3 個目の質問では、1 才の人が都市 4 から旅行を始めます。通れるのは 3 番目の道路だけなので、到達可能なのは都市 3 と都市 4 の 2 個です。

入力例 2

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

出力例 2

5
3
1

Score : 6 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In a country, there are N cities, numbered 1 through N.
The country has N - 1 roads, which are full of dangers. Thus, for each road, only people whose ages are within a certain range are permitted to traverse it; the i-th road connects City i and City i + 1 bidirectionally, and only people between the ages of L_i and R_i can traverse it.
You have started a travel agency in this country. Respond to Q queries from customers.
In the i-th query, given values A_i and B_i, find the number of cities that an A_i-year-old person can reach by starting at City B_i and traversing roads. (City B_i is also considered reachable.) We assume that the person does not get older during the trip.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

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

Sample Output 1

3
3
2

In the first query, a 3-year-old starts at City 1. The roads except the 3-rd one are passable, so the person can reach three cities: City 1 through 3.
In the second query, a 2-year-old starts at City 2. The roads except the 1-st one are passable, so the person can reach three cities: City 2 through 4.
In the third query, a 1-year-old starts at City 4. Only the third road is passable, so the person can reach two cities: City 3 and 4.

Sample Input 2

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

Sample Output 2

5
3
1