103656: [Atcoder]ABC365 G - AtCoder Office

Problem Statement

$N$ people work at the AtCoder office.

The office keeps records of entries and exits, and there have been $M$ entries and exits since the records began.

The $i$-th $(1\leq i\leq M)$ record is represented by a pair of integers $(T_i, P_i)$, indicating that at time $T_i$, the $P_i$-th person either entered the office if they were outside, or exited the office if they were inside.

It is known that all people were outside the office at the beginning of the records, and they are outside now.

Answer $Q$ queries in the following format.

For the $i$-th $(1\leq i\leq Q)$ query, you are given a pair of integers $(A_i, B_i)$. Find the total length of the periods during which both the $A_i$-th and $B_i$-th persons were inside the office since the records began.

Constraints

• $2\leq N\leq2\times10^5$
• $2\leq M\leq2\times10^5$
• $1\leq T_1\lt T_2\lt\dotsb\lt T_M\leq10^9$
• $1\leq P_i\leq N\ (1\leq i\leq M)$
• For every $1\leq p\leq N$, the number of indices $i$ such that $P_i=p$ is even.
• $1\leq Q\leq2\times10^5$
• $1\leq A_i\lt B_i\leq N\ (1\leq i\leq Q)$
• All inputs are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $i$-th line $(1\leq i\leq Q)$ should contain the answer to the $i$-th query.

Sample Input 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

Sample Output 1

20
0
20

The following diagram shows the time each of the three people spent inside the office.

The answers to each query are as follows:

• The 1st and 2nd persons were both inside the office from time $10$ to time $20$ and from time $70$ to time $80$. The lengths of these two periods are both $10$, so print the total, which is $20$.
• The 1st and 3rd persons were never inside the office at the same time, so print $0$.
• The 2nd and 3rd persons were both inside the office from time $40$ to time $60$. The length of this period is $20$, so print $20$.

Sample Input 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

Sample Output 2

18673
2107
15310
25720
17003
10317
16848

问题陈述

AtCoder办公室有N人工作。

办公室记录了进出情况，自记录开始以来已经有M次进出。

第i条（1≤i≤M）记录由一对整数（T_i, P_i）表示，这意味着在T_i时间，如果P_i人在外面，则他们进入办公室，如果他们在里面，则他们离开办公室。

已知记录开始时所有人都在办公室外面，现在他们也在外面。

回答以下格式的Q个查询。

对于第i个（1≤i≤Q）查询，给你一对整数（A_i, B_i）。找出自记录开始以来，A_i和B_i两个人都在办公室内的总时长。

约束条件

• 2≤N≤2×10^5
• 2≤M≤2×10^5
• 1≤T_1＜T_2＜…＜T_M≤10^9
• 1≤P_i≤N（1≤i≤M）
• 对于每个1≤p≤N，使得P_i=p的索引i的数量是偶数。
• 1≤Q≤2×10^5
• 1≤A_i＜B_i≤N（1≤i≤Q）
• 所有输入都是整数。

输入

输入从标准输入以以下格式给出：

N M
T_1 P_1
T_2 P_2
…
T_M P_M
Q
A_1 B_1
A_2 B_2
…
A_Q B_Q

输出

打印Q行。 第i行（1≤i≤Q）应包含第i个查询的答案。

示例输入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

下图显示了三个人在办公室内的时间。

每个查询的答案如下：

• 第1和第2个人都在办公室内的时间是从时间10到时间20，以及从时间70到时间80。这两个时段的长度都是10，所以打印总数，即20。
• 第1和第3个人从未同时在办公室内，所以打印0。
• 第2和第3个人都在办公室内的时间是从时间40到时间60。这个时段的长度是20，所以打印20。

示例输入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