/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 575 点
問題文
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 番目の高橋くんがどちらもオフィスの中にいた時間の長さを求めてください。
制約
- 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)
- どの 1\leq p\leq N についても、P _ i=p となる i は偶数個存在する
- 1\leq Q\leq2\times10 ^ 5
- 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq Q)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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 行目 (1\leq i\leq 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
3 人の高橋くんがオフィスの中にいた時間はそれぞれ以下の図のようになります。
それぞれの質問に対する答えは以下のようになります。
- 1 番目の高橋くんと 2 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 20 から時刻 30 の間と時刻 70 から時刻 80 の間の 2 回です。長さはどちらも 10 なので、これらの合計である 20 を出力してください。
- 1 番目の高橋くんと 3 番目の高橋くんが同時にオフィスの中にいたことはありません。よって、0 を出力してください。
- 2 番目の高橋くんと 3 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 40 から時刻 60 の間の 1 回です。長さは 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
Score : 575 points
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 20 to time 30 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