分数: 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