AcWing 802. 区间和-java-TreeSet+HashMap+数组
原题链接
简单
作者:
Astarion
,
2021-03-27 09:26:30
,
所有人可见
,
阅读 391
import java.io.*;
import java.util.*;
class Main {
static InputStreamReader isr = new InputStreamReader(System.in);
static BufferedReader in = new BufferedReader(isr);
static OutputStreamWriter osw = new OutputStreamWriter(System.out);
static BufferedWriter out = new BufferedWriter(osw);
static int N = 300010;
static int n, m, l, r, x, c;
static int[] a = new int[N];
static int[] s = new int[N];
//存储所有点
static Set<Integer> all = new TreeSet<>();
static List<Integer> ps = null;
//存储所有添加操作
static Map<Integer, Integer> adds = new HashMap();
//存储所有查询操作
static int idx;
static int[] ql = new int[N];
static int[] qr = new int[N];
static int findLoc(int x) {
int i = 0, j = ps.size() - 1;
while (i < j) {
int mid = (i + j) >> 1;
if (ps.get(mid) >= x) j = mid;
else i = mid + 1;
}
return i + 1;
}
public static void main(String[] args) throws IOException {
String[] strs = in.readLine().split(" ");
n = Integer.parseInt(strs[0]);
m = Integer.parseInt(strs[1]);
for (int i = 0; i < n; i++) {
strs = in.readLine().split(" ");
x = Integer.parseInt(strs[0]);
c = Integer.parseInt(strs[1]);
all.add(x);
if (adds.containsKey(x)) adds.replace(x, adds.get(x) + c);
else adds.put(x, c);
}
for (int i = 0; i < m; i++) {
strs = in.readLine().split(" ");
l = Integer.parseInt(strs[0]);
r = Integer.parseInt(strs[1]);
ql[idx] = l;
qr[idx++] = r;
all.add(l);
all.add(r);
}
ps = new ArrayList<>(all);
//添加操作
for (Map.Entry<Integer, Integer> entry : adds.entrySet()) {
x = entry.getKey();
c = entry.getValue();
int loc = findLoc(x);
a[loc] += c;
}
for (int i = 1; i <= ps.size(); i++) s[i] = s[i - 1] + a[i];
for (int i = 0; i < m; i++) {
l = ql[i];
r = qr[i];
out.write((s[findLoc(r)] - s[findLoc(l) - 1]) + "\n");
}
in.close();
isr.close();
out.flush();
out.close();
osw.close();
}
}