AcWing 802. 区间和
原题链接
简单
作者:
Phil.
,
2023-12-13 19:37:17
,
所有人可见
,
阅读 33
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // n次插入
int m = sc.nextInt(); // m次查询
int N = 300010;
int []a = new int[N];
int []s = new int[N]; // 前缀和数组
List<Integer> alls = new ArrayList<>(); // 记录所有的插入和查询,x,l,r
// 去重
List<Pair> add = new ArrayList<>(); // 存储n次操作
List<Pair> query = new ArrayList<>(); // 存储m次查询
// 输入n次增加操作,每次操作存入add中
for (int i = 0 ; i < n ; i ++){
int x = sc.nextInt();
int c = sc.nextInt();
add.add(new Pair(x,c));
alls.add(x);
}
// 输入m次询问,每次询问插入query集合中,因为l,r是求和的下标区间和,所以l,r都存入alls集合
for (int i = 0 ; i < m ; i ++){
int l = sc.nextInt();
int r = sc.nextInt();
query.add(new Pair(l,r));
alls.add(l);
alls.add(r);
}
Collections.sort(alls); // 对all中元素进行排序
int uniqe = unique(alls); // 对alls中元素进行去重
alls = alls.subList(0,uniqe); // 将去重后的alls长度范围的值重新赋值给alls
for(Pair item: add){
int index = find(item.first,alls);
a[index] += item.second;
}
for (int i = 1 ; i <= alls.size() ; i ++) s[i] = s[i - 1] + a[i]; // 求前缀和
for (Pair item : query){
int l = find(item.first,alls);
int r = find(item.second,alls);
System.out.println(s[r] - s[ l - 1 ]);
}
}
// 去重
public static int unique(List<Integer> list){
int j = 0;
for (int i = 0 ; i < list.size() ; i ++){
if ( i == 0 || list.get(i) != list.get(i - 1)){
list.set(j,list.get(i));
j ++;
}
}
return j; // 返回不重复的元素序列的最后一个值的下标
}
// 二分查找
public static int find(int x,List<Integer> list){
int l = 0;
int r = list.size() - 1;
while ( l < r){
int mid = (l + r) / 2;
if (list.get(mid) >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
}
class Pair{
int first;
int second;
public Pair(int x,int c ){
first = x;
second = c;
}
}
// 参考文献:https://www.acwing.com/activity/content/code/content/2029338/