E - 社内ランキング 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、ある会社の人事データを分析しています。この会社には N 人の社員がおり、各社員には数直線上の点で表される勤務地が割り当てられています。i 番目の社員の勤務地の座標は X_i、評価スコアは V_i です。なお、X_i はすべて異なります。評価スコアは大きいほど高い評価を表します。

高橋君は Q 個の調査依頼を受けています。j 番目の調査では、勤務地座標の範囲 [L_j, R_j] が指定されます。

各調査 j について、勤務地座標が L_j 以上 R_j 以下である社員の集合を S_j とします。S_j に含まれる各社員について、その社員の「順位」を次のように定めます。

  • S_j の中で、その社員より評価スコアが真に大きい社員の人数を k としたとき、その社員の順位は k + 1 とする。

すなわち、同じ評価スコアの社員が複数いる場合、それらはすべて同じ順位になります（いわゆる「同率順位」の方式です）。

例： ある調査において、S_j に含まれる社員の評価スコアが 5, 5, 3 の 3 人であった場合を考えます。

  • 評価スコア 5 の 2 人は、S_j の中で自分より真に大きい評価スコアを持つ社員が 0 人なので、順位はそれぞれ 0 + 1 = 1 です。
  • 評価スコア 3 の 1 人は、S_j の中で自分より真に大きい評価スコアを持つ社員が 2 人なので、順位は 2 + 1 = 3 です。

よって 3 人の順位はそれぞれ 1, 1, 3 となり、順位の総和は 1 + 1 + 3 = 5 です。

各調査について、S_j に含まれるすべての社員の順位の総和を求めてください。ただし、S_j が空集合（範囲内に社員がいない場合）のときは、総和は 0 とします。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq X_i \leq 10^9
  • 1 \leq V_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq 10^9
  • X_i はすべて異なる
  • V_i は異なるとは限らない
  • 入力はすべて整数である

入力

N Q
X_1 V_1
X_2 V_2
\vdots
X_N V_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、社員の数を表す整数 N と、調査の数を表す整数 Q が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目の社員の勤務地座標 X_i と評価スコア V_i が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、j 番目の調査の範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

Q 行出力してください。j 行目には、j 番目の調査における S_j に含まれるすべての社員の順位の総和を整数で出力してください。

入力例 1

3 3
1 5
2 5
3 3
1 3
2 3
1 1

出力例 1

5
3
1

入力例 2

4 3
1 10
3 20
5 10
7 30
2 6
8 10
1 7

出力例 2

3
0
9

入力例 3

8 5
2 7
4 3
6 7
8 5
10 3
12 9
14 7
16 1
1 16
4 12
6 6
3 9
1 2

出力例 3

32
14
1
6
1

入力例 4

10 8
5 100
11 50
17 100
23 75
29 50
35 200
41 75
47 100
53 50
59 200
1 59
5 35
20 50
11 47
35 59
1 10
29 29
17 41

出力例 4

47
19
14
25
14
1
1
14

入力例 5

1 1
1000000000 1000000000
1000000000 1000000000

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi is analyzing personnel data of a certain company. The company has N employees, and each employee is assigned a workplace represented as a point on a number line. The workplace coordinate of the i-th employee is X_i, and their evaluation score is V_i. All X_i are distinct. A higher evaluation score represents a better evaluation.

Takahashi has received Q investigation requests. The j-th investigation specifies a range of workplace coordinates [L_j, R_j].

For each investigation j, let S_j be the set of employees whose workplace coordinates are at least L_j and at most R_j. For each employee in S_j, their "rank" is determined as follows:

  • Let k be the number of employees in S_j whose evaluation score is strictly greater than that employee's evaluation score. Then that employee's rank is k + 1.

In other words, if multiple employees have the same evaluation score, they all receive the same rank (this is the so-called "standard competition ranking" method).

Example: Consider an investigation where S_j contains 3 employees with evaluation scores 5, 5, 3.

  • The 2 employees with evaluation score 5 each have 0 employees in S_j with a strictly greater evaluation score, so their ranks are 0 + 1 = 1 each.
  • The 1 employee with evaluation score 3 has 2 employees in S_j with a strictly greater evaluation score, so their rank is 2 + 1 = 3.

Thus, the ranks of the 3 employees are 1, 1, 3 respectively, and the sum of ranks is 1 + 1 + 3 = 5.

For each investigation, find the sum of ranks of all employees in S_j. If S_j is empty (no employees are within the range), the sum is 0.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq X_i \leq 10^9
  • 1 \leq V_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq 10^9
  • All X_i are distinct
  • V_i are not necessarily distinct
  • All input values are integers

Input

N Q
X_1 V_1
X_2 V_2
\vdots
X_N V_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains two space-separated integers: N, the number of employees, and Q, the number of investigations.
  • The following N lines each contain two space-separated values: the i-th line gives the workplace coordinate X_i and evaluation score V_i of the i-th employee.
  • The following Q lines each contain two space-separated values: the j-th line gives the left endpoint L_j and right endpoint R_j of the j-th investigation's range.

Output

Output Q lines. The j-th line should contain an integer representing the sum of ranks of all employees in S_j for the j-th investigation.

Sample Input 1

3 3
1 5
2 5
3 3
1 3
2 3
1 1

Sample Output 1

5
3
1

Sample Input 2

4 3
1 10
3 20
5 10
7 30
2 6
8 10
1 7

Sample Output 2

3
0
9

Sample Input 3

8 5
2 7
4 3
6 7
8 5
10 3
12 9
14 7
16 1
1 16
4 12
6 6
3 9
1 2

Sample Output 3

32
14
1
6
1

Sample Input 4

10 8
5 100
11 50
17 100
23 75
29 50
35 200
41 75
47 100
53 50
59 200
1 59
5 35
20 50
11 47
35 59
1 10
29 29
17 41

Sample Output 4

47
19
14
25
14
1
1
14

Sample Input 5

1 1
1000000000 1000000000
1000000000 1000000000

Sample Output 5

1