AT_abc365_g.[ABC365G] AtCoder Office

AtCoder 社的办公室里有 $N$ 个人。

在 AtCoder 社，办公室的进出记录被保存了下来，从开始记录到现在共发生了 $M$ 次进出事件。

第 $i$ 次（$1\leq i\leq M$）进出记录由整数对 $(T_i, P_i)$ 表示，表示在时刻 $T_i$，第 $P_i$ 个人如果在办公室外，则进入办公室；如果在办公室内，则离开办公室。

在开始记录时，所有人都在办公室外，并且现在所有人也都在办公室外。

请回答 $Q$ 个如下形式的问题。

第 $i$ 个（$1\leq i\leq Q$）问题给出整数对 $(A_i, B_i)$，请你求出在记录期间，第 $A_i$ 个人和第 $B_i$ 个人同时在办公室内的时间总长度。

输入按以下格式从标准输入给出。

$N$ $M$
$T_1$ $P_1$
$T_2$ $P_2$
$\vdots$
$T_M$ $P_M$
$Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

请输出 $Q$ 行，第 $i$ 行输出第 $i$ 个问题的答案。

限制条件

• $2\leq N\leq 2\times 10^5$
• $2\leq M\leq 2\times 10^5$
• $1\leq T_1 < T_2 < \dotsb < T_M \leq 10^9$
• $1\leq P_i \leq N\ (1\leq i\leq M)$
• 对于任意 $1\leq p\leq N$，使得 $P_i = p$ 的 $i$ 有偶数个
• $1\leq Q\leq 2\times 10^5$
• $1\leq A_i < B_i \leq N\ (1\leq i\leq Q)$
• 所有输入均为整数

样例解释 1

三个人在办公室内的时间如下图所示。

每个问题的答案如下：

• 第 1 个人和第 2 个人同时在办公室内的时间为时刻 $20$ 到 $30$ 以及时刻 $70$ 到 $80$，共两段。每段长度都是 $10$，所以总共 $20$，输出 $20$。
• 第 1 个人和第 3 个人从未同时在办公室内，输出 $0$。
• 第 2 个人和第 3 个人同时在办公室内的时间为时刻 $40$ 到 $60$，共一段，长度为 $20$，输出 $20$。

由 ChatGPT 4.1 翻译