問題リンク

解説

直接中央値がとなるようなsubstringを数え上げるのは大変です。

ここで

とするとを求めるのはBITなどを用いて簡単です

中央値がとなるようなsubstringはとなり求めることができました。

提出コード

codeforces.com