AcWing 802. 区间和 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-15 16:10:15
,
所有人可见
,
阅读 729
// 数值跨度大,但是位置稀疏 => 离散化
// 离散化 <= 去重 unique <= 排序
// 数组为10^5级别,求范围的和 => 前缀和
let arrN = [], arrM = [];
// 离散化的同时,去重+插入, 节约查找插入时间
let discretization = pairs => {
pairs.sort((a, b) => a[0] - b[0]);
let uniPairs = [pairs[0]], last = pairs[0];
for (let i = 1; i < pairs.length; i++) {
let curr = pairs[i];
if (curr[0] === last[0]) // 重复元素直接累加
last[1] += curr[1];
else {
uniPairs.push(curr);
last = curr;
}
}
return uniPairs;
}
let idxArr = [], sArr = [];
let init = () => {
let uniPairs = discretization(arrN);
uniPairs.unshift([0, 0]);
// 生成从1开始的索引数组
idxArr = uniPairs.map(val => val[0]);
// 生成从1开始的前缀和数组
uniPairs.map(x => x[1]).reduce((prev, curr) => {
let sum = prev + curr;
sArr.push(sum);
return sum;
}, 0);
}
let bsearchRL = (arr, checkMid) => {
let l = 0, r = arr.length - 1;
while (l < r) {
let mid = parseInt((l + r + 1) / 2);
if (checkMid(arr[mid])) l = mid;
else r = mid - 1;
}
return r;
}
let rangeSum = (l, r) => {
//注意边界
let i = bsearchRL(idxArr, mid => mid < l);
let j = bsearchRL(idxArr, mid => mid <= r);
return sArr[j] - sArr[i]
}
var buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputArgs = line =>
line.split(' ').filter(s => s !== '').map(x => parseInt(x));
process.stdin.on('end', function () {
let n = 0, m = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputArgs(line);
n = a[0], m = a[1];
} else if (lineIdx <= n) {
arrN.push(getInputArgs(line));
if (lineIdx === n) init();
} else if (lineIdx <= m + n) {
arrM.push(getInputArgs(line));
if (lineIdx === m + n) {
arrM.forEach(val => console.log(rangeSum(val[0], val[1])));
}
}
});
});