这里的保序的映射的意思:
1、大范围数轴上操作的坐标值Xi存入一个数组arr;
2、将询问的左右坐标l,r的值也存入到这个数组arr;
3、将arr中的所有元素排序并去重;
4、排序去重后,每个坐标值唯一且对应在arr中的一个下标,获取这个下标(二分法)index;
5、index即为Xi映射到小数组b中所在的下标值。
—可以这样处理的关键在于一开始就将所有的操作坐标值和询问坐标值存在一个数组中,然后按大小排序,
即操作坐标值和询问坐标值已经排好序,再映射的话也是按照原有的顺序映射!
---find方法:输入的是映射前的坐标值,返回的是该坐标值在alls中的下标(或者位置),这个下标也是映射后的坐标值!!!!
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
List<Integer> alls = new ArrayList<>();
List<Pairs> adds = new ArrayList<>();
List<Pairs> query = new ArrayList<>();
int[] a = new int[300010];
int[] s = new int[300010];
for(int i = 0 ; i<n ; i++){
int x = sc.nextInt();
int c = sc.nextInt();
adds.add(new Pairs(x,c));
alls.add(x);
}
for(int i = 0 ; i<m ; i++ ){
int l = sc.nextInt();
int r = sc.nextInt();
query.add(new Pairs(l,r));
alls.add(l);
alls.add(r);
}
//排序
Collections.sort(alls);
//去重
int unique = unique(alls);
alls = alls.subList(0,unique);
//映射
// for(int i = 0;i < adds.size(); i++){
// int index = find(alls,adds.get(i).first);
// a[index] = a[index] + adds.get(i).second;
// }
for (Pairs item:adds) {
int index = find(alls,item.first);
a[index] += item.second;
}
//前缀和
for(int i=1;i <= alls.size();i++){//alls.size() unique+1
s[i] = s[i-1] +a[i];
}
//询问结果
for(int i = 0;i<query.size();i++){
int res = 0;
int lIndex = find(alls,query.get(i).first);
int RIndex = find(alls,query.get(i).second);
res = s[RIndex]-s[lIndex-1];
System.out.println(res);
}
// for (Pairs item:query) {
// int l = find( alls,item.first);
// int r = find( alls,item.second);
// System.out.println(s[r] - s[l - 1]);
// }
}
static int unique(List<Integer> arr){
int j=0;
for(int i=0;i<arr.size();i++){
if(j == 0 || arr.get(i) != arr.get(i-1)){
arr.set(j,arr.get(i));
j++;
}
}
return j;
}
static int find(List<Integer> arr,int x){
int l=0,r=arr.size()-1;
while(l < r){
int mid = l+r >>1;
if(arr.get(mid) >= x){
r = mid;
}else{
l = mid+1;
}
}
return l+1;//从1开始
}
}
class Pairs{
int first;
int second;
public Pairs(int first,int second){
this.first = first;
this.second = second;
}
}