离散化 AC
区间长度很大，-10^9 ~ 10^9 无法开辟大小为 2 * 10^9 + 1 的数组去存储，故使用离散化来减少存储空间
查询次数和区间长度都很大，所以无法使用正常的求和去计算区间和，故使用前缀和快速计算

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    int N = 300000 + 10;    // 最大可能出现的下标个数
    int[] a = new int[N];   // 下标去重和排序后的数值数组
    int[] s = new int[N];   // 数组a的前缀和

    class Pair {    // 保留插入数据的关系
        int x;  
        int y;
        Pair(int x, int y) { this.x = x; this.y = y; }
    }

    ArrayList<Integer> all = new ArrayList<>();     // 待去重和排序的下标数组
    ArrayList<Pair> add = new ArrayList<>();        // add保留插入元素的下标和待插入的值
    ArrayList<Pair> query = new ArrayList<>();      // query保留查询区间的左右端点


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();

        Main ins = new Main();
        int[] ans = ins.solve(sc, n, m);

        for (int i = 0; i < m; i++) System.out.println(ans[i]);
        sc.close();
    }

    private ArrayList<Integer> unique() {   // 去重
        int n = all.size();
        ArrayList<Integer> ret = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (i == 0 || all.get(i) != all.get(i - 1)) ret.add(all.get(i));
        }

        return ret;
    }

    private int find(int x) {       // x表示待离散化的下标，需要在all数组中找到其离散化的位置
        int l = 0, r = all.size();  // 这里维护的是区间 [l, r)
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (all.get(mid) > x) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return l + 1;   // l + 1 为了适配前缀和下标从1开始计算，计算前缀和更方便(这里的下标是一定可以找到的，都是之前添加的，所以不用对下标为l的值进行特判)
    }

    private int[] solve(Scanner sc, int n, int m) {
        int[] ans = new int[m];

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            add.add(new Pair(x, y));
            all.add(x);
        }

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            query.add(new Pair(x, y));
            all.add(x); all.add(y);
        }

        Collections.sort(all);
        all = unique();

        for (Pair p : add) {
            int x = find(p.x);
            a[x] += p.y;
        }

        for (int i = 1; i <= all.size(); i++) s[i] = s[i - 1] + a[i];

        for (int i = 0; i < m; i++) {
            int l = find(query.get(i).x), r = find(query.get(i).y);
            ans[i] = s[r] - s[l - 1];
        }

        return ans;
    }
}