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$ 的区间内，运行区间完全包含在该区间内的火车数量。

输入输出样例 #1

输入 #1

2 3 1
1 1
1 2
2 2
1 2

输出 #1

3

输入输出样例 #2

输入 #2

10 3 2
1 5
2 8
7 10
1 7
3 10

输出 #2

1
1

输入输出样例 #3

输入 #3

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

输出 #3

7
9
10
6
8
9
6
7
8
10

说明/提示

限制条件

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