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$ 个问题的答案。

输入输出样例 #1

输入 #1

3 8
10 1
20 2
30 1
40 3
60 3
70 1
80 2
90 1
3
1 2
1 3
2 3

输出 #1

20
0
20

输入输出样例 #2

输入 #2

10 20
10257 9
10490 4
19335 1
25893 5
32538 9
33433 3
38522 9
40629 9
42896 5
52106 1
53024 3
55610 5
56721 9
58286 9
63128 3
70513 3
70977 4
74936 5
79883 9
95116 9
7
1 3
3 9
1 9
4 9
1 5
5 9
3 5

输出 #2

18673
2107
15310
25720
17003
10317
16848

说明/提示

限制条件

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