分数: 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