ABC107 D - Median of Medians - ツバサの備忘録

D - Median of Medians

提出コード
初めてBITを使った問題です。
この問題では、中央値となる条件をうまく言い換えていき、最終的に転倒数を求める問題に帰着させます。転倒数を求める段階で、BITを利用します。蟻本をみたらそこにも載っていた問題になります。
ある数xが数列A(要素数をMとします)の中央値になるには、少なくともAの中にx以上の数が(M+1)/2以上含まれている必要があります。
このようなxの中で最大の数が中央値になります。
今回はこれが2段階になっていて非常に分かりづらいのですが、中央値を並べた数列の要素数はn(n+1)/2なので、その中の中央値は以下の条件を満たしています。

最終的な数列の中に、x以上の数が{n(n+1)+2}/4個以上含まれている。

なので、全体としては、数列aに含まれる数字をソートし、その中で上の条件を満たしているかどうか、で二分探索をしていき、満たす数の中で最大のものを求める、という方針になります。x以上の数かどうか、が大切なので、中央値がxであるかどうか、はすでにあまり関係がなくなっています。では次に、上の条件を満たすかどうかの判定方法を探っていきます。

数列aのとある範囲について、左端と右端をlとrしたとき、その中にx以上の数が(r-l+1)/2個以上含まれているようなrとlの決め方を探すことになります。
(r-l+1)/2個以上というのは、結局

x以下数の個数<x以上の数の個数

という条件と等しくなります。よって、今求めたいものは

数列aのとある範囲について、x以下の数の個数<x以上の数の個数となるようなlとrの決め方が{n(n+1)+2}/4通り以上あるかどうか

になります。
そしてこれは、累積和をうまく活用すると、個数を綺麗に数えることができます。
x以上を1、x以下を-1として累積和をとると、x以上の個数とx以下の個数の差をうまく求めることができます。数列の初項からi項までの累積和を $S_i$ とすると、 $S_r - S_l$ が求めたいものになります。
しかし愚直にlとrを全探索すると時間がかかりすぎるので、BITの登場になります(このあたりからが転倒数を求めるアルゴリズムとほぼ同じものになります)。
BITを、「累積和が $S_i$ となるようなものの個数を表すもの」としてみると、rを固定し、 $S_r - S_l > 0$ となるようなlの決め方は、BITにおける $0$ から $S_r - 1$ までの総和となります。
あとはこれをrについて全探索(総和を求めて、BITに情報を追加、総和を求めてBITに情報を追加…の繰り返しです)すれば、 $O(N^{2})$ を $O(log N)$ に抑えることができます。

そして、 $S_r - S_l > 0$ となるようなlとrの決め方が{n(n+1)+2}/4通り以上あるようなxのうち、最大のものを二分探索で求めれば答えになります。