AcWing 802. 区间和
原题链接
简单
作者:
Tomato66
,
2021-01-14 23:09:36
,
所有人可见
,
阅读 330
备注:在JS中,排序不能使用默认参数进行排序,需要使用 (a,b)=>a-b回调
const rl = require('readline').createInterface({ input: process.stdin });
let co = 0;
let n;
let m;
/**
* @type {number[]}
*/
const a = [];
const s = [];
const add = [];
const query = [];
const set = new Set();
/**
* @description
* @param {string} line
*/
const readLine = line => line.trim().split(' ').map(Number);
rl.on('line', line => {
if (co === 0) [n, m] = readLine(line);
if (co >= 1 && co <= n) {
const [x, c] = readLine(line);
set.add(x);
add.push([x, c]);
}
if (co > n && co <= n + m) {
const [l, r] = readLine(line);
set.add(l);
set.add(r);
query.push([l, r]);
if (co === n + m) {
const alls = [...set];
alls.sort((a, b) => a - b);
const find = x => {
let l = 0;
let r = alls.length - 1;
while (l < r) {
const mid = parseInt((l + r) / 2, 10);
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
};
for (let i = 0; i <= alls.length; i++) {
a[i] = 0;
s[i] = 0;
}
add.forEach(([x, c]) => {
a[find(x)] += c;
});
for (let i = 1; i <= alls.length; i++) s[i] = s[i - 1] + a[i];
query.forEach(([l, r]) => {
console.log(s[find(r)] - s[find(l) - 1]);
});
}
}
co++;
});