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 翻译