离散化算法

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}

 import java.util.*;
public class Main {
    static int N=300010; //因为需要将所有x，l，r存在数组中，这样就是n + 2m <= 300000
    public static void main(String[] args)  {
        int []a=new int[N]; //存储坐标插入的值
        int []s=new int[N]; //存储a数组的前缀和
        List<Integer> alls=new ArrayList<>(); //存储（所有与插入和查询有关的）坐标 ,比如x、l、r
        List<Pairs> add = new ArrayList<>(); //用来存n次操作
        List<Pairs> query = new ArrayList<>(); //用来存m次询问
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m= sc.nextInt();
        for (int i = 0; i <n; i++) {
            int x=sc.nextInt();  int c= sc.nextInt();
            alls.add(x);
            add.add(new Pairs(x,c));
        }
        for (int i = 0; i <m; i++) {
            int l=sc.nextInt(); int r=sc.nextInt();
            alls.add(l); alls.add(r);
            query.add(new Pairs(l,r));
        }
        //利用HashSet对数组进行去重，然后排序
        alls=new ArrayList<>(new HashSet<>(alls));
        Collections.sort(alls);
        //执行n次插入
        for (Pairs pairs : add) {
            int index=find(pairs.first,alls);
            a[index]+= pairs.second;
        }
        //求前缀和
        for (int i = 1; i <=alls.size(); i++) {
            s[i]=s[i-1]+a[i];
        }
        //执行n次查询操作
        for (Pairs pairs : query) {
            int l=find(pairs.first, alls);
            int r=find(pairs.second, alls);
            System.out.println(s[r]-s[l-1]);
        }
    }
    public static Integer find(int x, List<Integer> alls){
    int l=0,r=alls.size()-1;
        while (l<r){
        int mid=l+r>>1;
          if(alls.get(mid)>=x) r=mid;
          else l=mid+1;
        }
        //考虑到求前缀和，下标手动加1
        return l+1;
    }
}
class Pairs {
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}