题目描述

区间和

JAVA 代码

import java.util.*;

class Main{
    static int N = 300010;
    static int[] a = new int [N];
    static int[] s = new int [N];

    static List<Integer> alls = new ArrayList<>();
    static List<PIIs> add = new ArrayList<>();
    static List<PIIs> query = new ArrayList<>();

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        for(int i =0; i < n ; i++){
            int x = sc.nextInt();
            int c = sc.nextInt();

            //每组添加 放入add 集合
            add.add(new PIIs(x,c));
            //把每个位置都加入到 alls集合
            alls.add(x);
        }

        for(int i = 0; i<m; i++){
            int l = sc.nextInt();
            int r = sc.nextInt();
            //每组区间和操作 放入 query集合
            query.add(new PIIs(l,r));
            //把每个位置都加入到 alls集合
            alls.add(l);
            alls.add(r);
        }

        //去重
        //排序
        Collections.sort(alls);
        //去重 返回 去重后的指针， 指针后的都为无用元素
        int u = unique(alls);
        //删除指针后的无用元素
        alls.subList(0, u);

        for(PIIs p : add){
            int x = find(p.getOne(), alls);
            a[x] += p.getTwo();
        }

        for(int i = 1; i<= alls.size(); i++){
            s[i] = s[i-1] + a[i];
        }

        for(PIIs p : query){
            int l = find(p.getOne(), alls);
            int r = find(p.getTwo(), alls);
            System.out.println(s[r] - s[l-1]);
        }
    }

    //二分查位置 x==> 在原数组中的位置, r+1 为在alls中的位置
    static int find(int x, List<Integer> alls){
        int l = 0;
        int r = alls.size();

        while(l<r){
            int mid = l + r >> 1;
            if(alls.get(mid) >= x){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return r+1;
    }


    //双指针去重
    static int unique(List<Integer> alls){
        int j = 0;
        for(int i = 0; i< alls.size(); i++ ){
            if(i==0 || alls.get(i) != alls.get(i-1)){
                alls.set(j++, alls.get(i));
            }
        }
        return j;
    }


}

class PIIs{

    int one;
    int two;

    PIIs(){
        one = 0;
        two = 0;
    }
    PIIs(int one, int two){
        this.one = one;
        this.two = two;
    }

    int getOne(){
        return this.one;
    }
    int getTwo(){
        return this.two;
    }

}