题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000

输入样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5

算法1

JAVA 代码

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lens = br.readLine().split(" ");
        int n = Integer.parseInt(lens[0]);
        int m = Integer.parseInt(lens[1]);
        //动态存所有，和动态存具体的键值对,以及前缀和查询所需要的l，r
        ArrayList<Integer> all = new ArrayList<>();
        Map<Integer, Integer> add = new HashMap<>();
        ArrayList<Integer> query = new ArrayList<>();
        int[] a = new int[300010];// 连续后的区间范围
        int[] s = new int[300010];//求前缀和的数组
        while(n-- > 0){
            String[] res = br.readLine().split(" ");
            int index = Integer.parseInt(res[0]);
            int value = Integer.parseInt(res[1]);
            add.put(index, add.getOrDefault(index, 0) + value);
            all.add(index);
        }
        while (m-- > 0){
            String[] res = br.readLine().split(" ");
            int l = Integer.parseInt(res[0]);
            int r = Integer.parseInt(res[1]);
            all.add(l);
            all.add(r);
            query.add(l);
            query.add(r);
        }
        Collections.sort(all);
        all = unique(all);
        for (Map.Entry<Integer, Integer> entry : add.entrySet()){
            a[find(all, entry.getKey())] = entry.getValue();   //all是连续后的区间，我们找到他的下标，放在a中，因为数组a才是我们想要的
        }
        for (int i = 1; i <= all.size(); i++){
            s[i] = s[i - 1] + a[i];
        }
        for (int i = 0; i < query.size(); i += 2){
            System.out.println(s[find(all, query.get(i + 1))] - s[find(all, query.get(i)) - 1]);
        }

    }
    //将离散的赋值键值对重新按照连续的区间进行赋值 如原来的3得坐标连续后可能就是2
    public static int find(ArrayList<Integer> all, int x){
        int l = 0, r = all.size() - 1;
        while (l < r) {
            int mid = r + l >> 1;
            if (all.get(mid) >= x) r = mid;        // x 是离散的下标位置，我们希望得到将它放在连续区间的下标位置
            else l = mid + 1;
        }
        return r + 1;//我们l是从0开始的，这里+1是为了我们进行前缀和处理时不用对i=0进行边界处理
    }
    public static ArrayList<Integer> unique(ArrayList<Integer> all) {//去重，如1,2,2,3
        ArrayList<Integer> res = new ArrayList<>();
        int j = 0;
        for (int i = 0; i < all.size(); i++){
            if (i == 0 || all.get(i) != all.get(i - 1)){
                res.add(all.get(i));
            }
        }
        return res;
    }

}