java 代码

import java.util.*;
public class Main{
    static int N=300010;
    static int[] a=new int[N];
    static int[] s=new int[N];//前缀和数组
    static List<int[]> adds=new ArrayList<>();
    static List<int[]> querys=new ArrayList<>();//所有询问
    static List<Integer> ids=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();
            adds.add(new int[]{x,c});
            ids.add(x);
        }
        for(int i=0;i<m;i++){
            int l=sc.nextInt(),r=sc.nextInt();
            ids.add(l);
            ids.add(r);
            querys.add(new int[]{l,r});
        }
        Collections.sort(ids);//排序

        int j=0;
        for(int i=1;i<ids.size();i++){//去重
            if(ids.get(i)!=ids.get(j)){
                ids.set(++j,ids.get(i));
            }
        }

        for(int i=ids.size()-1;i>j;i--){//去重后删多余的元素
            ids.remove(ids.size()-1);
        }

        for(int[] t:adds){
            int x=find(t[0]);
            int c=t[1];
            a[x]+=c;
        }
        for(int i=1;i<=ids.size();i++){//处理前缀和数组
            s[i]=s[i-1]+a[i];
        }

        for(int[] t:querys){
            int l=find(t[0]);
            int r=find(t[1]);
            System.out.println(s[r]-s[l-1]+" ");
        }

    }
    static int find(int x){//二分找元素离散化后的下标
        int l=0,r=ids.size()-1,mid;
        while(l<r){
            mid=l+(r-l)/2;
            if(ids.get(mid) < x){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return l+1;//下标从1开始，所以加1
    }
}