离散化
处理数据的值域很大，数量很少的问题
我们需要将数据映射到 一定空间中
如 a[] = 1, 3, 100, 2000, 500000，映射到 下标0, 1, 2, 3, 4
a[]中可能有重复数据先排序后去重,java 中利用set 先去重再排序- 如何算出
a[i]离散化后的值二分来做
AcWing 802. 区间和 原题链接
假定有一个无限长的数轴，数轴上每个坐标上的数都是0。
现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。
接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行，每行包含两个整数x和c。
再接下里 m 行，每行包含两个整数l和r。
输出格式
共m行，每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109−109≤x≤109, 1≤n,m≤1051≤n,m≤105, −109≤l≤r≤109−109≤l≤r≤109, −10000≤c≤10000−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
private static class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
int n = in.nextInt();
int m = in.nextInt();
List<Pair> adds = new ArrayList<>();
List<Pair> query = new ArrayList<>();
Set<Integer> set = new HashSet<>();
while (n-- > 0) {
int x = in.nextInt();
int y = in.nextInt();
adds.add(new Pair(x, y));
set.add(x);
}
while (m-- > 0) {
int x = in.nextInt();
int y = in.nextInt();
query.add(new Pair(x, y));
set.add(x);
set.add(y);
}
int[] arr = new int[set.size()];
int idx = 0;
for (int ii : set) {
arr[idx++] = ii;
}
//sort
Arrays.sort(arr);
//do add
int[] sum = new int[arr.length + 1];
for (Pair pp : adds) {
//map to 1,2,3,4......
sum[find(arr, pp.x) + 1] += pp.y;
}
for (int i = 1; i < sum.length; i++) {
sum[i] += sum[i - 1];
}
//do query
for (Pair pp : query) {
out.println(sum[find(arr, pp.y) + 1] - sum[find(arr, pp.x)]);
}
out.flush();
out.close();
}
private static int find(int[] arr, int tar) {
return Arrays.binarySearch(arr, tar);
}