AT_abc106_d [ABC106D] AtCoder Express 2

[problemUrl]: https://atcoder.jp/contests/abc106/tasks/abc106_d 高橋王国には, 東西にのびる $ 1 $ 本の線路がある. これに沿って $ N $ 個の都市があり, 西から順に都市 $ 1,\ 2,\ 3,\ \cdots,\ N $ と番号づけられている. AtCoder Express という会社は $ M $ 本の列車を保有しており, 列車 $ i $ は都市 $ L_i $ から都市 $ R_i $ の区間 ($ L_i\ =\ R_i $ の場合もある) を走っている. この王国の国王である高橋君は, $ Q $ 個のことに興味を持った. 具体的には, $ i=1,\ 2,\ 3,\ \dots,\ Q $ のときの以下の質問の答えを求めたくなった. - 都市 $ p_i $ から都市 $ q_i $ までの区間に, 走る区間が **完全に含まれる** 列車の本数. 言い換えれば, $ p_i\ \leq\ L_j $ と $ R_j\ \leq\ q_i $ が両方成り立つような列車 $ j $ の本数. 高橋君は天才である. しかし流石の彼でも, 膨大なデータを処理することはできない. 高橋君のために, $ Q $ 個の質問それぞれに対して答えを求めよ.

N/A

N/A

### 制約 - $ N $ は $ 1 $ 以上 $ 500 $ 以下の整数 - $ M $ は $ 1 $ 以上 $ 200\ 000 $ 以下の整数 - $ Q $ は $ 1 $ 以上 $ 100\ 000 $ 以下の整数 - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ M) $ - $ 1\ \leq\ p_i\ \leq\ q_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ Q) $ ### Sample Explanation 1 全ての列車の走る区間が, 都市 $ 1 $ から都市 $ 2 $ までの区間に含まれているので, この質問の答えは $ 3 $ となる. ### Sample Explanation 2 $ 1 $ 個目の質問は, 都市 $ 1 $ から $ 7 $ までの区間についてである. その区間に走る区間が完全に含まれている列車は, 列車 $ 1 $ のみである. $ 2 $ 個目の質問は, 都市 $ 3 $ から $ 10 $ までの区間についてである. その区間に走る区間が完全に含まれている列車は, 列車 $ 3 $ のみである.