java代码

import java.util.HashMap;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
    //所谓离散化 就是把一些数 映射到对于的1....的序列里面
    //原先离散化做法 排序 去重 二分 
    //用TreeSet 来代替排序和去重
    //用Map来代替二分
    static  int N=300010,n,m; //n+m的范围
    static  int a[]=new int[N];
    static  int s[]=new int[N];
    static  PII query[]=new PII[N];
    static  PII add[]=new PII[N];
    static TreeSet<Integer> set=new TreeSet<>(); //存每个x,l,r的下标
    public static  class  PII{
        int x,y;
        public PII(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++){
            int x=sc.nextInt();
            int c=sc.nextInt();
            add[i]=new PII(x,c);
            set.add(x);
        }
        for(int i=1;i<=m;i++){
            int l=sc.nextInt();
            int r=sc.nextInt();
            query[i]=new PII(l,r);
            set.add(l);
            set.add(r);
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        int idx=0; //表示x离散化后映射的下标 
        for(int i:set){ //这里的i是坐标 
            map.put(i,++idx);
        }
        for(int i=1;i<=n;i++){
            int x=add[i].x;
            int c=add[i].y;
            a[map.get(x)]+=c;
        }
        for(int i=1;i<=set.size();i++){ //前缀和
            s[i]=s[i-1]+a[i];
        }
        for(int i=1;i<=m;i++){
            int l=map.get(query[i].x);
            int r=map.get(query[i].y);
            System.out.println(s[r]-s[l-1]);
        }
    }
}