区間への足し算 (paizaランク A 相当)
クエリについてforループし、クエリの処理でforループをする、for二重ループで解くと、タイムオーバーになります。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//要素数 N とクエリの数 M
const [N, M] = lines[0].split(" ").map(Number);
//数列A
const A = lines[1].split(" ").map(num => Number(num));
//クエリについて
for (let i = 1; i <= M; i++) {
//各クエリの処理に用いる整数 l_i, u_i, a_i (1 ≦ i ≦ M)
const [l, u, a] = lines[i + 1].split(" ").map(Number);
// 要素番号が、l_i 以上、u_i 以下の全ての A の要素に、a_i を足す。
for (let j = l; j <= j; j++) {
A[j] += a;
}
}
console.log(A.join("\n"));
いもす法(imos法)について
いもす法(imos法)を使います。
要素番号が、l_i 以上、u_i 以下の全ての A の要素に、a_i を足す。
の場合、
例えば、配列add = Array(N+1).fill(0)を用意する。
前処理で、add[l_i]でa_iを足し、add[u_i+1]でa_iを引き、
for(i=0;i<N;i++)add[i+1] += add[i];で、累積和をつくる。
Aの要素に累積和の要素を足す、という流れです。
いもす法のイメージ
前処理で、add[l_i]でa_iを足し、add[u_i+1]でa_iを引き、
for(i=0;i<N;i++)add[i+1] += add[i];で、累積和をつくる、
というのが、いもす法のメインの処理です。
ここのイメージについて解説します。
例えば、
add = [0, 0, 0, 0, 0, 0, 0]
を用意して、いもす法でl_i=1からu_i=4までa_iを足すことにします。
add[l_i = 1]でa_iを足すと、
add = [0, a_i, 0, 0, 0, 0, 0]
となります。
累積和をつくるとき、add[i+1] += add[i]なので、a_iが次の要素に足され続けていきます。
どこで足すのを止めるか決めないと、最後までa_iが足され、
add = [0, a_i, a_i, a_i, a_i, a_i, a_i]
となります。
累積和を作る前に戻ります。
add[l_i = 1]でa_iを足したところです。
add = [0, a_i, 0, 0, 0, 0, 0]
a_iを足すのは、u_i=4までとすると、u_i+1=5でa_iを引いておきます。
add = [0, a_i, 0, 0, 0, -a_i, 0]
累積和を作ると、a_iが次々足されていきますが、
u_i+1=5の位置でa_i-a_i=0なので、
add = [0, a_i, a_i, a_i, a_i, 0, 0]
となります。a_iはu_i=4まで足されたことになります。
まとめると、l_i=1からu_i=4までa_iを足して、
add = [0, a_i, a_i, a_i, a_i, 0, 0]
としたい時、
add = [0, 0, 0, 0, 0, 0, 0]
を用意して、前処理でl_i=1でa_iを足し、u_i+1=5で-a_iして、
add = [0, a_i, 0, 0, 0, -a_i, 0]
累積和をつくれば、a_iが次々足されていって、u_i+1=5で0になり、
add = [0, a_i, a_i, a_i, a_i, 0, 0]
l_i=1からu_i=4までa_iを足したaddができます。
前処理で、add[l_i]でa_iを足し、add[u_i+1]でa_iを引き、
for(i=0;i<N;i++)add[i+1] += add[i];で、累積和をつくる
いもす法のイメージについての解説でした。
解答例
add配列の長さがN+1なのは、いもす法の前処理で、u_iがNのとき、u=N+1でadd[u] -= aするからです。範囲外にアクセスしないようにしています。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//数列 A の要素数 N と、条件に使う整数 M
const [N, M] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);
//Aに加えるadd
const add = Array(N + 1).fill(0);//N+1範囲外アクセス防ぐ
for (let i = 1; i <= M; i++) {
const [l, u, a] = lines[1 + i].split(" ").map(Number);
//いもす法の前処理
add[l - 1] += a;//l_iでa_iを足し
add[u] -= a;//u_i+1でa_iを引き
}
//累積和を作る
for (let i = 0; i < N; i++) {
add[i + 1] += add[i];
}
//addをAに加えて出力
for (let i = 0; i < N; i++) {
console.log(A[i] + add[i]);
}
最後の、累積和を作り、Aに加えて出力するところはまとめることができます。
//addをAに加えて出力しながら、累積和をつくる。
for (let i = 0; i < N; i++) {
//addをAに加える
console.log(A[i] + add[i]);
//累積和を作る
add[i + 1] += add[i];
}