← 返回题目列表

AtCoder · awc0040_e

E. 内部排名

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥正在分析某公司的人员数据。公司拥有 N 员工,每个员工都被分配一个工作场所,以数轴上的一个点表示。工作场所坐标 i第员工是 X_i,他们的评价分数是 V_i。全部 X_i 是不同的。评价分数越高表示评价越好。

高桥已收到 Q 调查请求。的 j-th 调查指定工作场所坐标范围 [L_j, R_j].

对于每项调查 j,让 S_j 是工作场所坐标至少为 L_j 最多 R_j。对于每个员工 S_j,他们的“排名”确定如下:

  • 让 k 是员工人数 S_j 其评估分数严格大于该员工的评估分数。那么该员工的职级就是 k + 1.

换句话说,如果多个员工的评价分数相同,则他们都获得相同的排名(这就是所谓的“标准竞争排名”方法)。

示例: 考虑进行一项调查,其中 S_j 包含 3 具有评估分数的员工 5, 5, 3.

  • 的 2 具有评估分数的员工 5 各有 0 员工 S_j 具有严格更高的评估分数,因此他们的排名是 0 + 1 = 1 每个。
  • 的 1 具有评估分数的员工 3 有 2 员工 S_j 具有严格更高的评估分数,因此他们的排名是 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
  • 第一行包含两个空格分隔的整数: N,员工人数,以及 Q,调查数量。
  • 以下 N 行每行包含两个空格分隔的值: i第行给出工作场所坐标 X_i 和评估分数 V_i 的 i第员工。
  • 以下 Q 行每行包含两个空格分隔的值: j第行给出左端点 L_j 和右端点 R_j 的 j第次调查的范围。

输出

输出 Q 行。的 j- 第行应包含一个整数,表示 中所有员工的等级总和 S_j 为 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