题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
近下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000
样例
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
算法
离散化+前缀和
时间复杂度
N = 所有坐标包括插入和查询的点的个数
1. TreeSet去重和排序: O(NlogN)
2. 离散化过程 O(N)
3. 离散化数组的(x, c)操作:n
4. 构造前缀和 O(N)
5. 完成询问 m*O(1) = O(m)
total 时间复杂度: O(NlogN)
空间复杂度
2O(N) + 2O(n) + 2O(m) = O(N)
Java 代码
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line0 = reader.readLine().split(" ");
int n = Integer.parseInt(line0[0]);
int m = Integer.parseInt(line0[1]);
Set<Integer> set = new TreeSet<>();
int[] indexes = new int[n]; // 保存了所有的x
int[] operate = new int[n]; // 保存了所有的c
for(int i = 0; i < n; i++){
String[] line = reader.readLine().split(" ");
int x = Integer.parseInt(line[0]);
int c = Integer.parseInt(line[1]);
indexes[i] = x;
operate[i] = c;
set.add(x);
}
int[] queryLeft = new int[m]; //保存了所有的l
int[] queryRight = new int[m]; //保存了所有的r
for(int i = 0; i < m; i++){
String[] line = reader.readLine().split(" ");
int l = Integer.parseInt(line[0]);
int r = Integer.parseInt(line[1]);
queryLeft[i] = l;
queryRight[i] = r;
set.add(l);
set.add(r);
}
// 现在set里面已经有了排好序的去了重的所有坐标,开始对坐标进行离散化
int[] mapping = new int[set.size()];
int k = 0;
for(Integer e : set){
mapping[k++] = e;
}
// 开始对离散化后的数组进行操作 利用之前保存的x(indexes数组中)找到离散化后的数组
// 位置进行操作(操作保存在了operate数组中)
int[] afterOpMapped = new int[set.size()];
// 构造差分 (starts with index of 0), afterOpMapped就是原数轴操作完后离散化的映射
for(int i = 0; i < n; i++){
int index = findIndex(mapping, indexes[i]);
afterOpMapped[index] += operate[i];
}
// 构造前缀和 (starts with index of 1;)
int[] preSum = new int[mapping.length + 1];
for(int i = 1; i <= afterOpMapped.length; i++){
preSum[i] = afterOpMapped[i - 1] + preSum[i - 1];
}
// 完成询问 所有针对原数轴的循环全部转换成对离散化映射数组的询问。
StringBuilder sb = new StringBuilder();
for(int i = 0; i < m; i++){
int l = findIndex(mapping, queryLeft[i]) + 1;
int r = findIndex(mapping, queryRight[i] + 1);
sb.append(preSum[r] - preSum[l - 1]);
sb.append("\n");
}
sb.deleteCharAt(sb.length() - 1);
System.out.println(sb.toString());
}
public static int findIndex(int[] mapping, int target){
int l = 0;
int r = mapping.length - 1;
while( l + 1 < r){
int mid = l + (r - l) / 2;
if(mapping[mid] < target){
l = mid;
}else{
r = mid;
}
}
return mapping[l] == target ? l : r;
}
}