JAVA 代码

import java.io.BufferedInputStream;
import java.util.*;

class Main{
    static int N = 300010;
    static int[] a = new int[N];
    static int[] s = new int[N];
    /**
     *一共有两个数组，三个列表
     * add列表存放成对数据<要加的位置，要加的数值>
     * query列表存放成对数据<位置起点、位置终点>
     * alls存放数轴中所有待映射的位置信息
     * 将alls排序，再用二分查找到位置对应的下标，相当于把alls中的位置数据信息映射到了小数组中的下标
     * a数组把这些小数组下标作为自己的下标，并在此基础上填充要加的值
     * 经过这么映射加填充，可以理解为原来的位置上存上数了
     * s数组存放前缀和
    */
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int m = in.nextInt();
        List<Pairs> add = new ArrayList<>();
        List<Pairs> query = new ArrayList<>();
        List<Integer> alls = new ArrayList<>();
        //读取所有的数
        for(int i = 0; i < n; i++){
            int o = in.nextInt();
            int k = in.nextInt();
            add.add(new Pairs(o, k));
            alls.add(o);
        }
        for(int i = 0; i < m; i++){
            int o = in.nextInt();
            int k = in.nextInt();
            query.add(new Pairs(o,k));
            alls.add(o);
            alls.add(k);
        }
        //排序 去重
        Collections.sort(alls);
        int unique = unique(alls);
        alls= alls.subList(0, unique);
        //填充
        for(int i = 0; i < n; i ++){
            int index = find(alls, 0, alls.size() - 1,add.get(i).first);
            a[index] += add.get(i).last;
        }
        //前缀和
        for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
        //区间和
        for(Pairs item : query){
            int l = find(alls, 0, alls.size() - 1, item.first);
            int r = find(alls, 0, alls.size() - 1, item.last);
            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(List<Integer> a, int l, int r, int target){

        while(l != r){
            int mid = (l + r) / 2;
            if(a.get(mid) >= target) r = mid;
            else l = mid + 1;
        }
        return l + 1; //考虑前缀和+1.
    }
}
class Pairs{
    public int first;
    public int last;
    public Pairs(int first, int last){
        this.first = first;
        this.last = last;
    }
}