← 返回题目列表

AtCoder · abc106_d

D. AtCoder快车2

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

在高桥王国,有一条东西向的铁路和 N 沿线城市,编号 1, 2, 3, ..., N 从西到东。 一家名为 AtCoder Express 拥有 M 火车,还有火车 i 从城市出发 L_i 前往城市 R_i (有可能 L_i = R_i)。 高桥王感兴趣以下内容 Q 事项:

  • 运行的列车数量 严格在 来自城市的部分 p_i 前往城市 q_i,即列车数量 j 这样 p_i \leq L_j 和 R_j \leq q_i.

虽然他是天才,但是这数据太多了,他一个人无法处理。找到每个问题的答案 Q 查询帮助他。

约束

  • 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)

输入

输入由标准输入按以下格式给出:

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.


示例输入 1

2 3 1
1 1
1 2
2 2
1 2

示例输出 1

3

由于所有列车均在从市区出发的路段内运行 1 前往城市 2,唯一查询的答案是 3.


示例输入 2

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

示例输出 2

1
1

第一个查询位于 City 部分 1 to 7。只有一趟列车严格在该路段内运行: 火车 1。 第二个查询位于 City 部分 3 to 10。只有一趟列车严格在该路段内运行: 火车 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