AcWing 802. 区间和 Java版
原题链接
简单
作者:
Luo_4
,
2020-09-18 09:39:30
,
所有人可见
,
阅读 538
Java 代码
import java.util.*;
public class Main{
static List<Integer> allis;
static class Pair{
int first,second;
public Pair(int x,int c){
first=x;
second=c;
}
}
public static int find(int x){
int l=0,r=allis.size()-1;
while(l <= r){
int mid=l+(r-l)/2;
if(allis.get(mid) >= x){
r = mid-1;
}else{
l = mid+1;
}
}
return l+1;
}
public static List<Integer> unique(List<Integer> allis){
int j=0;
for(int i=0;i<allis.size();i++){
if(i==0 || allis.get(i)!=allis.get(i-1)){
allis.set(j++,allis.get(i));
}
}
return allis.subList(0,j);
}
public static void main(String[] args){
Scanner scann = new Scanner(System.in);
int n = scann.nextInt();
int m = scann.nextInt();
int[] a=new int[3*n+1];
int[] s=new int[3*n+1];
List<Pair> add = new ArrayList<>();
List<Pair> query = new ArrayList<>();
allis = new ArrayList<>();
//处理插入
while (n-- > 0){
int x=scann.nextInt();
int c=scann.nextInt();
add.add(new Pair(x,c));
allis.add(x);
}
//处理询问
while (m-- > 0){
int l=scann.nextInt();
int r=scann.nextInt();
query.add(new Pair(l,r));
allis.add(l);
allis.add(r);
}
Collections.sort(allis);
allis=unique(allis);
for(Pair p:add){
int idx=find(p.first);
a[idx]+=p.second;
}
for(int i=1;i<=allis.size();i++){
s[i] = s[i-1] + a[i];
}
for(Pair p:query){
int l=find(p.first);
int r=find(p.second);
System.out.println(s[r] - s[l-1]);
}
}
}