AcWing 798. 差分矩阵 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-14 10:24:47
,
所有人可见
,
阅读 702
/*
1. 把原矩阵看成0,用插入操作构造差分矩阵
2. 进行实际插入操作
3. 利用矩阵前缀和公式求得原矩阵
初始差分矩阵的构造理解:
把原矩阵看成0,则差分矩阵也为0;通过差分插入操作后,差分矩阵必然继续满足差分性质;
差分 为 前缀和 的 逆函数。
重点:插入操作
包括子矩阵的右下大区域 - 子矩阵下方 - 子矩阵右方 + 重叠区域
*/
let diffMtx = [];
let insert = (x1, y1, x2, y2, c) => {
// 包括子矩阵的右下大区域 - 子矩阵下方 - 子矩阵右方 + 重叠区域
diffMtx[x1][y1] += c;
diffMtx[x2 + 1][y1] -= c;
diffMtx[x1][y2 + 1] -= c;
diffMtx[x2 + 1][y2 + 1] += c;
}
var buf = '';
process.stdin.on('readable', function () {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputArgs = line => {
return line.split(' ').filter(s => s !== '').map(x => parseInt(x));
}
process.stdin.on('end', function () {
// n 行 m列
let n = 0, m = 0, q = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let firstline = getInputArgs(line);
n = firstline[0];
m = firstline[1];
q = firstline[2];
//初始化 diff
let k = n + 2;
while (k-- > 0) {
diffMtx.push(Array(m + 2).fill(0));
}
}
else if (lineIdx <= n) {
//原矩阵索引从0开始,构造后的差分矩阵从1开始
let row = getInputArgs(line);
row.unshift(0);
row.push(0);
for (let j = 1; j <= m; j++) {
// 把原值依次插入,相当于插入一个 1x1 的矩阵
insert(lineIdx, j, lineIdx, j, row[j]);
}
}
else {
if (q > 0) {
let op = getInputArgs(line);
insert(...op);
}
q--;
if (q === 0) {
//这里行列不要搞混 row = n, column = m
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
diffMtx[i][j] += diffMtx[i][j - 1] + diffMtx[i - 1][j] - diffMtx[i - 1][j - 1];
}
}
diffMtx.shift();
diffMtx.pop();
for (let i = 0; i < n; i++) {
diffMtx[i].shift();
diffMtx[i].pop();
console.log(diffMtx[i].join(' '))
}
}
}
});
});