Codeforces 519D

こどふぉす

問題

a〜zの26個のアルファベットの重みが与えられる。
ある文字列が与えられたとき、長さ1以上の部分文字列で「両端のアルファベットが同じ」かつ「両端を除いたアルファベットの重みの和が0」であるようなものがいくつあるか？

  • 10^5<=アルファベットの重み<=10^5

文字列の長さ<=10^5

考え方

文字aが位置1,4,5に出現したとすると、1〜4、4〜5、1〜5の部分文字列の両端を除いた重みの和が0であることを求めなければならない。
BITを使うと、0〜xの合計値が高速に求められるので、x〜yは0〜x-1と0〜yを求めて引けば求められる。
しかし、m個出現した場合、両端の組み合わせを求めるのに単純にはO(m^2)かかってしまい、間に合わない。


ここで、上記の例で5が出現した場合、0〜4(両端を抜くので)の合計値を求めておくと、0〜2(両端を抜くので)と0〜5(両端を抜くので)の合計値が洗い出されていれば、差分を取っても0でないといけないので、合計値が同じになるものが何個あるか数えればよい。
mapなどに合計値と個数を入れておけば、それまでに出現したところの合計値で、0〜現在の位置までの合計値が一緒になる個数がわかり、O(mlog(m))程度でカウントできる。