Movie Festival Queries

题目描述

在一个电影节中，将放映 $n$ 部电影。你知道每部电影的开始和结束时间。 你的任务是处理 $q$ 个查询，查询的形式为：如果你在特定时间到达并在特定时间离开电影节，你最多能看多少部电影？ 如果第一部电影在第二部电影开始前或恰好在第二部电影开始时结束，则可以观看两部电影。你可以在到达时恰好开始第一部电影，也可以在最后一部电影结束时恰好离开。

输入格式

第一行包含两个整数 $n$ 和 $q$：电影数量和查询数量。 接下来有 $n$ 行描述电影。每行有两个整数 $a$ 和 $b$：电影的开始和结束时间。 最后有 $q$ 行描述查询。每行有两个整数 $a$ 和 $b$：你的到达和离开时间。

输出格式

对于每个查询输出最多可以观看的电影数量。

4 3
2 5
6 10
4 7
9 10
5 9
2 10
7 10

0
2
1

提示

$1 \le n,q \le 2 \cdot 10^5$ $1 \le a < b \le 10^6$

标签: CSES1664|区间查询

来源

CSES1664|区间查询