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 翻译