区间和
- 1.题目
- 2.基本思想
- 3.代码实现
1.题目
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
− 1 0 9 ≤ x ≤ 1 0 9 , −10^9≤x≤10^9, −109≤x≤109,
1 ≤ n , m ≤ 1 0 5 , 1≤n,m≤10^5, 1≤n,m≤105,
− 1 0 9 ≤ l ≤ r ≤ 1 0 9 , −10^9≤l≤r≤10^9, −109≤l≤r≤109,
− 10000 ≤ c ≤ 10000 −10000≤c≤10000 −10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
2.基本思想
3.代码实现
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(), m = sc.nextInt();int N = 300010;//int[] a = new int[N], s = new int[N];//ArrayList<Integer> alls = new ArrayList<>();//将所有用到的数存到alls数组 可能有重复元素 需要 排序 + 去重List<Pairs> add = new ArrayList<>(); //用来存储n次 操作List<Pairs> query = new ArrayList<>();//用来存储m次 查询for (int i = 0; i < n; i++) {int x = sc.nextInt(), c = sc.nextInt();add.add(new Pairs(x, c));alls.add(x);}for (int i = 0; i < m; i++) {int l = sc.nextInt(), r = sc.nextInt();query.add(new Pairs(l, r));alls.add(l);alls.add(r);}Collections.sort(alls);//排序 int unique = unique(alls);//去重alls.subList(0, unique);//将去重后的List保存下来，截取到不重复的值for (Pairs item : add) {//对应位置加上 cint 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 (Pairs item : query) {int l = find(item.first, alls), r = find(item.second, alls);System.out.println(s[r] - s[l - 1]);}}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;}static int find(int x, List<Integer> list) {//二分查找int l = 0, r = list.size() - 1;while (l < r) {int mid = (l + r) >> 1;if (list.get(mid) >= x) r = mid;else l = mid + 1;}return l+1 ;// +1 便于 之后前缀和计算}
}class Pairs {int first, second;public Pairs(int first, int second) {this.first = first;this.second = second;}
}
