离散化
当一个数组中的长度很短,但是每个数却非常大,那么就可以使用离散化进行映射关系
例如有一个数组[50,500,900,1500,20000,320000,540000],我们可以找到映射关系来储存这个数组以及对数组的值进行操作
1.先将数组进行去重和排序,从小到大
2.再利用去重排序过的数组下标来将每一个数映射到新的容器里
3.b[] = {1,2,3,4,,5,6,7} 是储存原数组的映射数组
4.可以通过映射关系来操作数组
【例题:】
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
−10^9^≤x≤10^9^,
1≤n,m≤10^5^,
−10^9^≤l≤r≤10^9^,
−10000≤c≤10000
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
【思路:】
1.现将n次操作和m次询问所涉及到的下标存储在Set集合里(Java去重复)
2.然后转化成Object类型的数组a,并且使用Arrays.sort排序
3.再将储存好的n操作遍历一遍,每次操作的x下标进行映射,利用二分来求在a数组中和x相等的数的下标
4.再将求得的映射下标在新数组s里进行操作
5.求得新数组s的前缀和
6.遍历m个区间和,每次区间和为s[i] - s[j - 1]
【代码:】
import java.io.*;
import java.util.*;
public class Main {
static int N = 300010;
static Object[] a = new Object[N];
static int[][] f = new int[N][2], t = new int[N][2];
static int[] s = new int[N];
static int n, m;
//获取当前下标得映射
private static int found(int x) {
int l = 0, r = a.length - 1;
while(l < r) {
int mid = l + r >> 1;
if((int)a[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
public static void main(String[] args) throws IOException{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
HashSet<Integer> set = new HashSet<>();
String[] str1 = read.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
//储存添加下标和数
for (int i = 1; i <= n; i++) {
str1 = read.readLine().split(" ");
int x, c;
x = Integer.parseInt(str1[0]);
c = Integer.parseInt(str1[1]);
f[i][0] = x;
f[i][1] = c;
set.add(x);
}
//储存求和区间
for (int i = 1; i <= m; i++) {
str1 = read.readLine().split(" ");
int l, r;
l = Integer.parseInt(str1[0]);
r = Integer.parseInt(str1[1]);
t[i][0] = l;
t[i][1] = r;
set.add(l);
set.add(r);
}
//去重加排序
a = set.toArray();
Arrays.sort(a);
//给区间赋值
for (int i = 1; i <= n; i++) {
int x = found(f[i][0]);
s[x] += f[i][1];
}
//获取前缀和
for (int i = 1; i <= set.size(); i++) s[i] += s[i - 1];
for (int i = 1; i <= m; i++) {
int x = found(t[i][0]);
int y = found(t[i][1]);
System.out.println(s[y] - s[x - 1]);
}
}
}