AT_ndpc2026_e 夏休み

你的暑假今天开始，总共持续 $N$ 天。 有 $M$ 个事件。第 $i$ 个事件从第 $A_i$ 天早上开始，到第 $B_i$ 天晚上结束。 你有 $Q$ 个询问。每个询问会给出两个整数 $L$ 和 $R$，你需要回答以下问题： > 你打算在第 $L$ 天到第 $R$ 天期间，尽可能多地参加事件。 > 但是，你不能在事件中途加入或离开。因此，你不能同时参加时间段重叠的多个事件，也不能参加在 $L$ 天之前开始或在 $R$ 天之后结束的事件。 > 如果你选择性地参加事件，最多可以参加多少个事件？

输入从标准输入中给出，格式如下： > $N$ $M$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $A_M$ $B_M$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\cdots$ $\mathrm{query}_Q$ 每个询问格式如下： > $L$ $R$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

### 样例解释 1 例如，在第一个查询中，你可以参加第 1 个和第 2 个事件，这是最大值。 ### 数据范围 - $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$ - 所有输入值都是整数。 由 ChatGPT 5 翻译