描述
可以用TreeMap这个集合,完成去重、排序、二分查找,所以代码要少一些。
解释一下TreeMap:底层是红黑树实现的。可以简单理解为有序的HashMap。
getOrDefault(key, default): 获取key对应的value,如果没有key,则返回默认值default。
ceilingEntry(key): 返回大于等于key的Entry(二分)
lowerEntry(key): 返回小于key的Entry(二分),注意,如果没有key,会报空指针异常。
java 代码
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[][] q = new int[m][2];
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++) {
int add1 = in.nextInt();
int add2 = in.nextInt();
map.put(add1, map.getOrDefault(add1, 0) + add2);
}
for (int i = 0; i < m; i++) {
q[i][0] = in.nextInt();
map.put(q[i][0], map.getOrDefault(q[i][0], 0));
q[i][1] = in.nextInt();
map.put(q[i][1], map.getOrDefault(q[i][1], 0));
}
Object[] keys = map.keySet().toArray();
for (int i = 1; i < keys.length; i++) { // 前缀和
map.put((Integer) keys[i], map.get(keys[i-1]) + map.get(keys[i]));
}
for (int i = 0; i < m; i++) {
if(q[i][0] == (Integer)keys[0]){ // 避免空指针异常
System.out.println(map.ceilingEntry(q[i][1]).getValue());
}else{
System.out.println(map.ceilingEntry(q[i][1]).getValue() - map.lowerEntry(q[i][0]).getValue());
}
}
}
}
其实没必要把查询区间put进map里