AT_abc106_d [ABC106D] AtCoder Express 2

高桥王国有一条东西走向的铁路，沿着这条铁路有 $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$ 的区间内，有多少列火车的运行区间**完全包含**在这个区间内。换句话说，有多少列火车 $j$ 满足 $p_i \leq L_j$ 且 $R_j \leq q_i$。 高桥君是个天才，但即使是他也无法处理如此庞大的数据。请你帮高桥君回答这 $Q$ 个问题。

输入按以下格式从标准输入读入： > $N$ $M$ $Q$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_M$ $R_M$ > $p_1$ $q_1$ > $p_2$ $q_2$ > $\vdots$ > $p_Q$ $q_Q$

输出 $Q$ 行。第 $i$ 行输出对于城市 $p_i$ 到城市 $q_i$ 的区间内，运行区间完全包含在该区间内的火车数量。

### 限制条件 - $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$） ### 样例解释 1 所有火车的运行区间都被包含在城市 $1$ 到城市 $2$ 的区间内，所以这个问题的答案是 $3$。 ### 样例解释 2 第 $1$ 个问题是关于城市 $1$ 到 $7$ 的区间。在该区间内，只有第 $1$ 列火车的运行区间被完全包含。第 $2$ 个问题是关于城市 $3$ 到 $10$ 的区间。在该区间内，只有第 $3$ 列火车的运行区间被完全包含。 由 ChatGPT 4.1 翻译