802. 区间和

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

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

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

输入格式

第一行包含两个整数 n� 和 m�。

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

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

输出格式

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

数据范围

−109≤x≤109−109≤�≤109,
1≤n,m≤1051≤�,�≤105,
−109≤l≤r≤109−109≤�≤�≤109,
−10000≤c≤10000−10000≤�≤10000

输入样例：

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

输出样例：

8
0
5

import java.util.*;
public class Main {
    static int N = 300010;//一个N +两个M 所以要开30万

    static List<Integer> alls = new ArrayList<>();//存放的是离散化后的list 实际上就是用来存所有的下标x,l,r;
    static List<Pair> query = new ArrayList<>(), adds = new ArrayList<Pair>();//用来存n次操作 和 m次查询
    static int a[] = new int[N], s[] = new int[N];//a是存放的数值数组  s是前缀和的数组
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();//n次操作
        int m = scan.nextInt();//m次询问
         //输入n次操作，每次操作存入add集合中，然后将下标x存入alls集合中
        for(int i = 0 ; i < n ; i++){
            int x = scan.nextInt();
            int c = scan.nextInt();
            alls.add(x);
            adds.add(new Pair(x, c));
        }
        //输入m次询问，每次询问存入query集合中，因为l,r是求和的下标区间和，所以l,r都存入alls集合中。
         for(int i = 0 ; i < m ; i ++ ){
            int l = scan.nextInt();
            int r = scan.nextInt();
            query.add(new Pair(l,r));
            alls.add(l);
            alls.add(r);
        }
          
        // Java的离散化操作
        alls = new ArrayList<>(new HashSet<>(alls));//通过hashset去重
        Collections.sort(alls); //排序，现在alls集合中存的是x，l，r所有值
        //增强for循环 for(元素类型 变量名 ： 数组或者集合) 缺点：无下标，简单。
        for(Pair item : adds){
            int index = find(item.first);//
            a[index] += item.second;//
        }

        for(int i = 1 ; i <= alls.size() ; i ++ ) s[i] = s[i-1] + a[i]; //这是前缀和公式代码

        for(Pair item : query){
            int l = find(item.first); // 
            int r = find(item.second); // 
            System.out.println(s[r] - s[l-1]); // 
        }


 
        
    }
    
    //二分查找（find函数中是使用了二分来查找x在alls中的下标+1，因为需要符合我们要用的前缀和公式，
    //要让下标不是从0输出，最低的下标是1，符合前缀和的从1开始，所以输出的值加1）
   static int find(int x) {//寻找第一个大于等于x的数 ||第一个小于等于x的数
        int l = 0, r = alls.size() - 1;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(alls.get(mid) <= x)
                l = mid;
            else r = mid - 1;
        }
        return l + 1;
    }
}   
//这是一个Pair类，用来存操作的类
   class Pair{
        int first;
        int second;
        public Pair(int x,int c){
            this.first = x;
            this.second = c;
        }
    }