AtCoder Express 2

题目描述

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

在从城市 $p_i$ 到城市 $q_i$ 的区间内严格运行的列车数量，也就是满足 $p_i \leq L_j$ 且 $R_j \leq q_i$ 的列车 $j$ 的数量。

尽管他非常聪明，但这些数据太多，难以自己处理。请找出每个查询的答案以帮助他。

输入格式

输入从标准输入给出，格式如下： $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

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

1
1

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

提示

$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$ 到城市 $2$ 的区间内运行，唯一一个查询的答案是 $3$。
第一个查询是区间从城市 $1$ 到 $7$。在该区间内严格运行的列车只有一辆：列车 $1$。 第二个查询是区间从城市 $3$ 到 $10$。在该区间内严格运行的列车只有一辆：列车 $3$。

标签: AtCoder|abc106D

来源

AtCoder|abc106D