![問題概要
N*M(N, M≦1000) の行列 X があり、初期状態では
全ての要素が 0 。
以下のクエリが Q(≦10^6) 個あるので、全て処理し
た後の行列を求めよ。
X[i, j] += max( 0, d - (| i – a | + | j – b |) )
1 ≦ d ≦ max(N, M), 1≦a≦N, 1≦b≦M](https://image.slidesharecdn.com/pyramid-121024111227-phpapp02/85/Pyramid-2-320.jpg)
![いもす法って？
区間への加算を、定数箇所の更新だけで済ませる。
加算された値を具体的に知りたくなったら累積和
をとる。
愚直 いもす法
更新 ( 加算 ) O(n) O(1)
O(H*W)
参照 O(1) O(n)
(a[i]=?) O(H*W)
本問題のように、更新が多く参照が少ない状況に
適している。](https://image.slidesharecdn.com/pyramid-121024111227-phpapp02/85/Pyramid-4-320.jpg)
More Related Content
What's hot (20)
Similar to Pyramid (17)
Pyramid
- 1. Pyramid 原案： komiya
- 2. 問題概要 N*M(N, M≦1000) の行列 X があり、初期状態では 全ての要素が 0 。 以下のクエリが Q(≦10^6) 個あるので、全て処理し た後の行列を求めよ。 X[i, j] += max( 0, d - (| i – a | + | j – b |) ) 1 ≦ d ≦ max(N, M), 1≦a≦N, 1≦b≦M
- 3. 解法 一部でいもす法と呼ばれているアイデアを使う。 JOI 界隈では頻出？
- 4. いもす法って？ 区間への加算を、定数箇所の更新だけで済ませる。 加算された値を具体的に知りたくなったら累積和 をとる。 愚直 いもす法 更新 ( 加算 ) O(n) O(1) O(H*W) 参照 O(1) O(n) (a[i]=?) O(H*W) 本問題のように、更新が多く参照が少ない状況に 適している。
- 5. いもす法って？ 結局何をやっているのか？ 累積和の逆変換 ( 階差数列 ) を利用している。 +1 +1 +1 +1 +1 O(n) 箇所の更新が必要 階差数列 累積和 どっち向きの変換も 計算量 O(n) +1 -1 定数箇所の更新で済む 処理が軽いので、加算クエリが多 いときはこっちの世界で処理する 方が効率良い
- 6. いもす法って？ さっきの話は 2 次元以上にも拡張できる！ 2 1 -1 2 3 2 累積和 0 3 2 2 6 7 -2 1 -1 逆変換 0 5 5 変換に必要な計算量は O(H*W)
- 7. 範囲和の処理 例えば次のようなクエリを処理することを考えよう。 +1 +1 +2 +1 +1 +2 +3 +2 +1 +1 +2 +1 +1
- 8. 範囲和の処理 累積和の逆変換を行うと次のような区間和になる。 +1 -1 +1 -1 +1 -1 -1 +1 -1 +1 -1 +1
- 9. 範囲和の処理 今度は斜め方向に累積和の逆変換をとる。 +1 -1 +1 -1
- 10. 範囲和の処理 こっち方向でも逆変換。 -1 -1 +1 +1
- 11. 細かいところ：端の処理 ピラミッド型範囲和が端で途切れると処理が面倒 なので、行列を拡大して考えると楽。 実際の行列 の範囲
- 12. 解法まとめ 端で途切れるのを防ぐため、行列を拡大する。 Q 個のクエリを処理する。右下方向と左下方向に 分けてそれぞれ定数箇所に値を加える。 右下方向と左下方向で累積和をとる。 右下方向と左下方向の累積和を重ね合わせる。 重ね合わせたものの 2 次元累積和をとる。
- 13. おまけ 同様の手法で次のような加算クエリも処理できる。 +1 +1 +1 +1 +1 +1 +2 +2 +2 +1 +1 +2 +3 +2 +1 +1 +2 +2 +2 +1 +1 +1 +1 +1 +1 Let's 逆変換 !