区間の数え上げ / 1 : 累積〇〇シフト
区間の数え上げに関する技術のひとつであり、最近のコンテストでも出題された「左を固定して右を高速に数え上げ」の一種について。 一般に$ Ο(N^2)な数え上げをどうにかして高速にしたいときで、なおかつ左端を固定したときの右端に単調性がない(左端が固定されても、右端としてあり得るものが$ 1箇所と限らない)場合の手法としてあり得る。
なお、左端を固定すると右端が高々$ 1箇所とか、右端がある場所までは必ず題意を満たし、それより末尾側に行くと必ず題意を満たさない、とかいう状態になる場合には想定解が区間の数え上げ / 2 : 尺取り法である場合が多い。 今まで私は累積〇〇の〇〇が「和」以外だったものは見かけていないので、ここでも累積和の問題を扱う。
具体例
最初に全ての累積和をとる。するともちろん、左端が$ A_1であるときの答えがわかる。
累積和が$ 0になっていれば$ A_1からそこまでの区間は総和が$ 0となる。
左端が$ A_2, A_3, \ldots, A_Nである場合の答えを毎回累積和するともちろん$ Ο(N^2)になるが、試しに$ A_2からの累積和をとってみると、全ての要素が$ A_1だけ小さくなっていることが見て取れる。
入力例 $ 1を実例として挙げると、
$ A_1からの累積和は $ \{1, 4, 0, 2, 4, 2\}であり、
$ A_2からの累積和は $ \{\times, 3, -1, 1, 3, 1\}であり、
$ A_3からの累積和は $ \{\times, \times, -4, -2, 0, -2\}となる。
なお、累積和した値を毎回上記の性質に合わせて$ A_1引く、$ A_2引くなどとしていると$ Aの全要素が互いに相異なる場合に$ Ο(N^2)となる。ここで、累積和を更新せずに欲しい値の方を更新することで計算量が$ Ο(N)や$ Ο(N \log N)になる。
なお、$ \logがつくかどうかはmap次第であり、JavaのHashMapなどを使えば当然$ \logはなくなる。
というのも、累積和は$ \{1, 4, 0, 2, 4, 2\}という値のままで、$ A_3, A_4, A_5という区間が条件を満たすということをカウントしたいとすると、$ A_3を左端として見ているときは、$ A_1からの累積和は$ A_1 + A_2 = 4であってほしい。これを定式化すると、$ A_iを左端として見ている時は、累積和が$ \Sigma_{k=1}^{i-1}であればよい。
具体的には、
まず、最初にとった累積和の値と出現回数をmapにカウントする。説明を簡単にするため、累積和を取った後の数列を$ Bとする。
累積和が$ Xになっていれば区間の総和が$ 0である、というような$ Xを変数にもつ。最初はもちろん$ X=0である。
$ i = 1, 2, \ldots, Nについて、
mapを使って累積和が$ Xであるような場所の個数を答えに加算する。
$ Xに$ A_iを足す。
map上でも$ B_iの個数を$ 1減らす。でないと、区間の左右が入れ替わっている(要は$ A_l, A_{l+1}, \ldots, A_rという区間を考える時に$ l>rのような状態)場合までカウントしてしまう。
以上の処理を順に行うと答えが得られる。
類題