D - AtCoder Express 2

得分：400 分

问题描述

在高桥王国，有一条东西方向的铁路，沿线有 $N$ 个城市，从西到东编号为 $1$、$2$、$3$、…、$N$。 公司名为 AtCoder Express 拥有 $M$ 列火车，第 $i$ 列火车从第 $L_i$ 号城市到第 $R_i$ 号城市运行（可能有 $L_i = R_i$）。 高桥王对以下 $Q$ 个问题感兴趣：

• 运行 完全区间 在从第 $p_i$ 号城市到第 $q_i$ 号城市的火车数，即满足 $p_i \le L_j$ 且 $R_j \le q_i$ 的 $j$ 的个数。

虽然高桥王很聪明，但这个数据量对他来说太庞大了。 帮助他回答这 $Q$ 个问题。

约束

• $N$ 是一个介于 $1$ 和 $500$ 之间的整数（包含边界值）。
• $M$ 是一个介于 $1$ 和 $200 \ 000$ 之间的整数（包含边界值）。
• $Q$ 是一个介于 $1$ 和 $100 \ 000$ 之间的整数（包含边界值）。
• $1 \le L_i \le R_i \le N$ （$1 \le i \le M$）
• $1 \le p_i \le q_i \le N$ （$1 \le i \le Q$）

输入

在标准输入中以下面的格式给出输入：

$N$ $M$ $Q$

$L_1$ $R_1$

$L_2$ $R_2$

$:$

$L_M$ $R_M$

$p_1$ $q_1$

$p_2$ $q_2$

$:$

$p_Q$ $q_Q$

输出

输出 $Q$ 行。 第 $i$ 行应该包含运行 完全区间 在从第 $p_i$ 号城市到第 $q_i$ 号城市的火车数。

2 3 1
1 1
1 2
2 2
1 2

3

由于所有火车都运行在从第 $1$ 号城市到第 $2$ 号城市的区间内，唯一的查询的答案是 $3$。

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

1
1

第一个查询是在从第 $1$ 号城市到第 $7$ 号城市的区间内。在此区间内只有一列火车完全运行：火车 $1$。 第二个查询是在从第 $3$ 号城市到第 $10$ 号城市的区间内。在此区间内只有一列火车完全运行：火车 $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

7
9
10
6
8
9
6
7
8
10