分数: 3 点
问题陈述
你的暑假从今天开始,持续时间 N 天。
有 M 事件。 i第一个活动于当天早上开始 A_i 并于当天晚上结束 B_i.
你被给予 Q 查询。在每个查询中,您都会得到两个整数 L 和 R,您需要回答以下问题:
您决定从当天起参加尽可能多的活动 L 到今天 R.
但是,您无法中途加入或离开活动。因此,您不能参加多个时间段重叠的活动,也不能参加当天之前开始的活动 L 或当天后结束 R.
如果您选择最佳的活动,您最多可以参加多少场活动?
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq N
- 1 \leq L \leq R \leq N
- 所有输入值均为整数
输入
输入由标准输入给出,格式如下:
N M Q
A_1 B_1
A_2 B_2
\vdots
A_M B_M
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均按以下格式给出:
L R
输出
打印 Q 行。对于 i第行,输出答案 i第一个查询。
示例输入 1
5 3 3 1 3 4 5 2 2 1 5 1 1 3 5
示例输出 1
2 0 1
例如,在第一个查询中,您可以参加第 1 个和第 2 个活动,这是最多的。
示例输入 2
9 13 8 4 6 1 5 8 9 5 6 1 7 4 9 4 6 2 8 5 6 5 8 2 6 3 7 1 3 5 7 5 7 5 7 3 4 1 8 2 6 6 8 8 9
示例输出 2
1 1 1 0 2 1 0 1