题目描述

blablabla

样例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class IntervalSum {
    private static int N = 300010;
    static class Pair {
        int key;
        int value;

        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        int[] a = new int[N];

        List<Integer> arr = new ArrayList<Integer>(N);
        List<Pair> add = new ArrayList<>();
        List<Pair> query = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] pair = br.readLine().split(" ");
            int key = Integer.parseInt(pair[0]);
            int value = Integer.parseInt(pair[1]);
            add.add(new Pair(key, value)); 
            arr.add(key);
        }

        for (int i = 0; i < m; i++) {
            String[] pair = br.readLine().split(" ");
            int l = Integer.parseInt(pair[0]);
            int r = Integer.parseInt(pair[1]);
            query.add(new Pair(l, r)); 
            arr.add(l);
            arr.add(r);
        }

        //对arr中存储的所有数，做离散化操作
        //1、排序
        //2、去重
        Collections.sort(arr);
        int index  = unqiue(arr);
        arr = arr.subList(0, index);

        //求出add过程中操作的数，离散化后的位置，并记录下各值
        for (Pair item : add) {
            int index1 = find(item.key, arr);
            a[index1] += item.value;
        }


        //求出前缀和,这里下标0处默认为0，防止区间left=0时，0-1 = -1出错
        int[] sum = new int[arr.size() + 1];
        for (int i = 1; i <= arr.size(); i++) {
            sum[i] = a[i] + sum[i - 1];
        }

        //输出所求区间的区间和 = sum[r] - sum[l - 1]
        //先找出left和right离散后的映射位置
        for (Pair item : query) {
            int l = find(item.key, arr);
            int r = find(item.value, arr);

            int res = sum[r] - sum[l - 1];

            System.out.println(res);
        }

        br.close();

    }

    //去重，返回去重后的元素个数
    private static int unqiue(List<Integer> arr) {
        int number = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (i == 0 || arr.get(i) != arr.get(i - 1)) { //第一次遍历的时候i= 0  ||逻辑或,发生短路，后面的代码不运行
                arr.set(number, arr.get(i));
                number++;
            }
        }
        return number;
    }

    //找出下标离散后的位置；二分法查找
    private static int find(int x, List<Integer> arr) {
        int l = 0;
        int r = arr.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (arr.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + 1; //映射的下标为1， 2， 3， 4……前缀和是从1开始计算的
    }

}