AcWing 802. 区间和
原题链接
简单
作者:
土豆有点
,
2020-04-15 11:16:24
,
所有人可见
,
阅读 577
import java.util.*;
import java.util.stream.Collectors;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[300001];
int[] s = new int[300001];
List<Integer> axis = new ArrayList<>();
List<Pairs> add = new ArrayList<>(); //用来存n次操作
List<Pairs> query = new ArrayList<>(); //用来存m次询问
for(int i = 0; i < n; i++){
int x = sc.nextInt();
int c = sc.nextInt();
add.add(new Pairs(x,c));
axis.add(x);
}
for(int i = 0; i < m; i++){
int l = sc.nextInt();
int r = sc.nextInt();
query.add(new Pairs(l, r));
axis.add(l);
axis.add(r);
}
//axis数组去重
axis = axis.stream().sorted().distinct().collect(Collectors.toList());
for (Pairs item : add) {
int index = find(item.first, axis);
a[index] += item.second;
}
for (int i = 1; i <= axis.size(); i++) s[i] = s[i - 1] + a[i];
for (Pairs item : query) {
int l = find(item.first, axis);
int r = find(item.second, axis);
System.out.println(s[r] - s[l - 1]);
}
}
static int find(int x, List<Integer> list) {
int l = 0;
int r = list.size()-1;
while (l < r) {
int mid = (l + r +1) >> 1;
if (list.get(mid) > x) {
r = mid-1;
} else {
l = mid;
}
}
return l+1; //因为要考虑到前缀和
}
}
class Pairs {
int first;
int second;
public Pairs(int first, int second) {
this.first = first;
this.second = second;
}
}