题目描述

区间和acwing802

样例

算法1: 离散化

import java.util.*;

public class Main {

    static final int N = 300010;//n + 2m最大值为30w
    static int[] a = new int[N], s = new int[N];//a离散后的数组，s前缀和
    static List<List<Integer>> add = new ArrayList<>();//添加操作
    static List<List<Integer>> query = new ArrayList<>();//查询操作
    static List<Integer> alls = new ArrayList<>();//需要进行离散化的集合
    static int n, m;

    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(), v = sc.nextInt();
            add.add(Arrays.asList(x, v));
            alls.add(x);//对数轴进行离散化
        }

        for (int i = 0; i < m; i++) {
            int l = sc.nextInt(), r = sc.nextInt();
            query.add(Arrays.asList(l, r));
            alls.add(l);//同上
            alls.add(r);
        }
        //去重加排序
        alls = new ArrayList<>(new HashSet<>(alls));
        Collections.sort(alls);
        //预处理添加操作
        for (List<Integer> item : add) {
            int idx = find(item.get(0));
            a[idx] += item.get(1);
        }
        //计算前缀和
        for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
        //处理查询操作
        for (List<Integer> item : query) {
            int l = find(item.get(0)), r = find(item.get(1));

            System.out.println(s[r] - s[l - 1]);
        }
    }
    //整数二分
    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;//返回+1方便处理前缀和
    }
}

算法2: 使用TreeMap

Java 代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        TreeMap<Integer, Integer> a = new TreeMap<>();//默认按照key升序

        while (n-- > 0) {
            int x = in.nextInt(), c = in.nextInt();
            a.put(x, a.getOrDefault(x, 0) + c);//直接放即可
        }

        TreeMap<Integer, Integer> s = new TreeMap<>();//前缀和
        int currentSum = 0;
        for (Map.Entry<Integer, Integer> entry : a.entrySet()) {
            currentSum += entry.getValue();
            s.put(entry.getKey(), currentSum);//按照key升序
        }

        while (m-- > 0) {
            int l = in.nextInt(), r = in.nextInt();
            //lowerKey(l)返回<l的最大key
            int leftSum = s.lowerKey(l) == null ? 0 : s.get(s.lowerKey(l));
            //floorEntry(r)返回<=r的最大entry
            int rightSum = s.floorEntry(r) == null ? 0 : s.get(s.floorEntry(r).getKey());

            System.out.println(rightSum - leftSum);
        }
    }
}