当区间比较稀疏(跨度很大用不了这么多空间)的时候使用离散化

数组开300010的原因:
- n个x,m个l,m个r –> n+2m
- m,n的范围都是[1,10^5]
- 也就是300000 再多开10个
- 即300010

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

public class Main {
    public static final int N = 300010;
    public static int[] a = new int[N], s = new int[N];//前者存储对应位置插入的值,后者存储a数组的前缀和
    public static List<Integer> alls = new ArrayList<>();//存取所有会用到的下标
    public static ArrayList<tmp> ind = new ArrayList<>(), query = new ArrayList<>();
    static InputReader in = new InputReader();
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n = in.nextInt(), m = in.nextInt();
        for (int i = 0; i < n; i++) {
            int x = in.nextInt(), c = in.nextInt();
            ind.add(new tmp(x, c));//存入n次 "添加"操作 数对
            alls.add(x);//存入 "添加"操作 涉及到的下标
        }
        for (int i = 0; i < m; i++) {
            int l = in.nextInt(), r = in.nextInt();
            query.add(new tmp(l, r));//存入"查询"操作数对
            alls.add(l);//添加"查询"操作涉及到的下标
            alls.add(r);;//添加"查询"操作涉及到的下标
        }

        //因Set中没有get()方法,无法获取指定下标的值,
        //这里将List转成Set(去重)再转成List
        alls = new ArrayList<Integer>(new HashSet<Integer>(alls));
        //排序
        Collections.sort(alls);

        for (tmp item : ind) {//添加操作
            int index = find(item.a);//index为"插入"操作离散化后的下标
            a[index] += item.b;//存储对应位置插入的值
        }
        for (int i = 1; i <= alls.size(); i++) s[i] = a[i] + s[i - 1];//求a数组的前缀和
        for (tmp item : query) {//查询操作
            int l = find(item.a);//l为"查询"操作离散化后的下标
            int r = find(item.b);//r为"查询"操作离散化后的下标
            System.out.println(s[r] - s[l - 1]);//求指定区间的和 -> 前缀和
        }


            out.close(); //不关闭输出流的话，控制台会没有输出，所以一定要关，in最好也关，不过实测没有因为不关in出过问题
    }

    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;//如果没有指定泛型的话默认是Object,其无法与int进行比较
            else l = mid + 1;
        }
        return l + 1;//+1是因为后面要求前缀和
    }

    static class InputReader {
        private StringTokenizer st;
        private BufferedReader bf;

        public InputReader() {
            bf = new BufferedReader(new InputStreamReader(System.in));
            st = null;
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return bf.readLine();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}

class tmp {
    int a;
    int b;

    public tmp(int a, int b) {
        this.a = a;
        this.b = b;
    }
}

这个题搞了好久才搞明白TAT,手写题解配合代码食用