QUPC2018-E:Treeone - 思考の墓場

最近よく見るやつ。

問題概要

長さ $N$ の数列 $\{A_i\}$ が与えられる。その数列の連続する部分列であって，総和が0であるものの個数を数列のたぴさと呼ぶ。数列のうち1つの値を自由に変えられるとき，あり得るたぴさの最小値を求めよ。
E - Treeone

解法

「数列の連続する部分列であって，総和が0であるものの個数」と聞いたら，累積和 $\{S_i\}$ を考えるのが定石である。その個数は， $S_i=S_j$ となる $(i,j) (i\leqq j)$ の組の個数に等しい。つまりは，ある条件を満たす区間の数である。このうち， $A_k$ の値を一つだけ変えて，どれだけそういう区間を減らせるかということを考えよう。答えは

「元の数列のたぴさ」から「 $A_k$ を変えることで減らせる区間の数の最大値」を引いたもの

である。「元の数列のたぴさ」の効率的な計算については，A - Zero-Sum Rangesがそのものなので参照していただきたい。
$A_k$ の値をうまく変えることによって， $i\leqq k \leqq j$ を満たす区間 $(i,j)$ については，条件を満たさないようにできる。例えば， $A_k$ を5000兆とかにすれば，もともと和が0だった区間の和が5000兆くらいになる。また， $A_k$ を5000兆に変えたことによって，和が0でなかったの区間の和が0になることもない。 $k$ を含む区間については5000兆という数字がでかすぎて和が0になりようがないし， $k$ を含まない区間は $A_k$ が5000兆になったところで何の影響もない。よって，各 $k$ について，「 $i\leqq k \leqq j$ を満たす区間 $(i,j)$ であって， $S_i=S_j$ なるものの個数」が効率的に求まればよい。
これにはimos法と呼ばれるものを使う(imos法を知らない方は調べてください)。各 $i$ について，「 $i$ から始まる条件をみたす区間の数」足し算し，「 $i$ で終わる条件をみたす区間の数」を引き算する。その後，順に累積和を取っていけば，各 $k$ に対して，「 $k$ を含む条件をみたす区間の数」がわかる。また

「 $i$ から始まる条件をみたす区間の数」は「 $i\leqq j$ であって， $S_i=S_j$ をみたすものの個数」に等しい
「 $i$ で終わる条件をみたす区間の数」は「 $j\leqq i$ であって， $S_j=S_i$ をみたすものの個数」に等しい

よって，各 $S_i$ の値が全部でいくつあるかを調べておき， $i$ が小さい順に上の計算をしてけばよい(詳細はコードを見た方がわかると思う)。実装上注意すべきは，単に $S_i=0$ となるような場合(つまり， $A_1+\cdots +A_i=0$ となる場合)を数えるために， $S_0=0$ から計算を行うところである。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3441083

$S_i$ がどんな値かわからないため，mapを用いている
「 $i\leqq j$ であって， $S_i=S_j$ をみたすものの個数」や「 $j\leqq i$ であって， $S_j=S_i$ をみたすものの個数」は適当に引き算すれば求まるので，直接調べる必要はない

方針はすぐだったが，変なところでバグらせて足を引っ張ってしまった。反省。