問題

$N$ 個の要素をもつ数列 $A$ が与えられる。たぴさを数列の連続する部分列のうち、総和が $0$ である個数とする。数列のある $1$ つの要素を任意の数に変更できるとき、たぴさの最小値を求めよ。

制約

もとの数列について部分列の総和が $0$ になる個数については、Zero-Sum Ranges と同じである。

ある要素 $A_i$ を INF に変更する操作について考える。 $A_i$ がもとの数列で $0$ になる部分列の区間の中に含まれる場合、その部分列の総和が $0$ でなくなる。もとの数列で $0$ になる部分列の区間の中に含まれなかった場合は変わらない。

よってたぴさの最小値を求めるとき、 $A_i$ がもとの数列で総和が $0$ になる部分列の区間に含まれる最大数をもとめて、それを引けば良い。

f:id:d_tutuz:20181021152753p:plain

ある要素に対して、どれだけの区間が含まれるのか？という情報を求める必要がある。これは imos 法で求めることができる。

累積和の数列を $sum$ としておく。

これらは左、右の要素から累積和をとることでそれぞれ求めることができる。あとは imos 法を適応させて区間の重なりを求めれば解くことができる。