import java.util.*;
import java.io.*;
class Main {
// 存储 将要离散化的数据
static List<Integer> alls = new ArrayList<>();
public static int find(int x) {
int l = 0, r = alls.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
public static int unique(List<Integer> list) {
// 将list中排好序的元素,进行去重,最后返回长度,用于remove
int j = 0;
for (int i = 0; i < list.size(); i++) {
if (i == 0 || list.get(i) != list.get(i - 1)) list.set(j++, list.get(i));
}
return j;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new InputStreamReader(System.in));
int n = sc.nextInt();
int m = sc.nextInt();
// 存储 用于add的数据
List<int[]> addc = new ArrayList<>();
// 存储 用于查询的数据
List<int[]> query = new ArrayList<>();
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int c = sc.nextInt();
addc.add(new int[]{x , c});
alls.add(x);
}
for (int i = 0; i < m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
query.add(new int[]{l, r});
alls.add(l);
alls.add(r);
}
// 排序
Collections.sort(alls);
// 去重
int tmp = unique(alls);
alls.subList(tmp, alls.size()).clear();
int N = alls.size() + 1;
int[] a = new int[N];
int[] s = new int[N];
// 处理插入
for (int[] item: addc) {
int x = find(item[0]);
a[x] += item[1];
}
// 预处理前缀和
for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
// 处理询问
for (int[] item: query) {
int l = find(item[0]), r = find(item[1]);
System.out.println(s[r] - s[l - 1]);
}
}
}
hashset去重+ stream流输出
import java.util.*;
import java.util.stream.*;
class Main {
static List<Integer> alls = new ArrayList<>();
public static int find(int x){
int l = 0, r = alls.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
List<int[]> addc = new ArrayList<>();
List<int[]> query = new ArrayList<>();
// 使得alls 不存入重复数据
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
int x, c;
x = sc.nextInt();
c = sc.nextInt();
addc.add(new int[]{x, c});
if (set.add(x)) alls.add(x);
}
for (int i = 0; i < m; i++) {
int l, r;
l = sc.nextInt();
r = sc.nextInt();
query.add(new int[]{l, r});
if (set.add(l)) alls.add(l);
if (set.add(r)) alls.add(r);
}
// 排序
Collections.sort(alls);
int N = alls.size();
int[] a = new int[N + 1];
int[] s = new int[N + 1];
for (int[] i: addc) {
int x = find(i[0]);
a[x] += i[1];
}
for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
query.forEach(i -> System.out.println(s[find(i[1])] - s[find(i[0]) -1]));
}
}