AT_past202012_n 旅行会社

[problemUrl]: https://atcoder.jp/contests/past202012-open/tasks/past202012_n ある国には $ 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 $ 自身を含む) の数を求めてください。旅行中この人の年齢は変わらないものとします。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目の質問に対する答えを出力せよ。

### 注意 この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ - 入力は全て整数 ### Sample Explanation 1 $ 1 $ 個目の質問では、$ 3 $ 才の人が都市 $ 1 $ から旅行を始めます。$ 3 $ 番目の道路以外は通れるので、到達可能なのは都市 $ 1 $ から都市 $ 3 $ までの $ 3 $ 個です。 $ 2 $ 個目の質問では、$ 2 $ 才の人が都市 $ 2 $ から旅行を始めます。$ 1 $ 番目の道路以外は通れるので、到達可能なのは都市 $ 2 $ から都市 $ 4 $ までの $ 3 $ 個です。 $ 3 $ 個目の質問では、$ 1 $ 才の人が都市 $ 4 $ から旅行を始めます。通れるのは $ 3 $ 番目の道路だけなので、到達可能なのは都市 $ 3 $ と都市 $ 4 $ の $ 2 $ 個です。