Codeforces Round #496 (Div. 3) - E2. Median on Segments (General Case Edition)

問題リンク

解説

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

ここで f(x) := 中央値がx以上のsubstringの数

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

中央値が mとなるようなsubstringは f(m) - f(m + 1)となり求めることができました。

提出コード

codeforces.com