离散化

点的值范围很大，但数量有限，所以不能直接开数组，需要将每个点做映射。

Java代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * @author jeffery.ma
 * @date 2022/10/24 13:56
 */

class Pair implements Comparable<Pair> {
    public int x;
    public int y;

    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Pair o) {
        return x - o.x;
    }
}

public class Main {
    public static int n, m;
    public static List<Integer> alls = new ArrayList<>();
    public static List<Pair> adds = new ArrayList<>();
    public static List<Pair> querys = new ArrayList<>();
    public static int find(int x) {
        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;
        }
        return l + 1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i ++) {
            int x = sc.nextInt();
            int c = sc.nextInt();
            adds.add(new Pair(x, c));
            alls.add(x);
        }
        for (int i = 0; i < m; i ++) {
            int l = sc.nextInt(), r = sc.nextInt();
            alls.add(l);
            alls.add(r);
            querys.add(new Pair(l, r));
        }
        alls = alls.stream().distinct().sorted().collect(Collectors.toList());
        int[] s = new int[alls.size() + 1];
        for (int i = 0; i < n; i ++) {
            int idx = find(adds.get(i).x);
            s[idx] += adds.get(i).y;
        }
        for (int i = 1; i < s.length; i ++) {
            s[i] += s[i - 1];
        }
        for (int i = 0; i < m; i ++) {
            int l = find(querys.get(i).x), r = find(querys.get(i).y);
            System.out.println(s[r] - s[l - 1]);
        }
    }
}