https://beta.atcoder.jp/contests/arc101/tasks/arc101_b
長さ$N$の数列が与えられる。この数列の、考えられるすべての連続部分列($\frac{N(N+1)}{2}$個ある)の中央値で数列を作ったとき、その中央値を求めよ。ここで、数列の中央値とは、昇順でソートしたときに前から$\frac{N}{2}+1$番目の値を指す。
長さ$N$の数列に対してある値$X$が中央値になるためには、数列のなかに$X$以下の数字が$\frac{N}{2}+1$個以上なくてはならず、その条件を満たす$X$たちのなかで一番小さいものが中央値になる。よって、与えられた数列の連続部分列の中央値たちの中に、ある値$X$以下のものがいくつあるかということがある程度高速にわかれば、中央値を二分探索できることになる。
ここで、部分列の中央値を並べた数列の中に$X$以下の数字がいくつあるかを数えるためには、それぞれの中央値が$X$以下かどうかということだけわかればいい(正確な値は知らなくていい)ので、それぞれの部分列の中央値が$X$以下かどうかを知る方法を考える。
ある部分列(長さ$M$とする)の中央値が$X$以下であるということは、その部分列のなかに$X$以下の値が$\frac{M}{2}+1$個以上あるということである。このことを調べるためには、もとの数列について$X$以下の数字を$-1$、それ以外の数字を$+1$に置換して和をとればわかる。この和が負であれば、もともとの数列に$X$以下の値が$\frac{M}{2}+1$個以上ある、すなわちその部分列の中央値は$X$以下であるということになる。
以上のようなことをすべての部分列に対して行っていては結局間に合わないので、一気に数えたい。ここで、区間の和を素早くとるには累積和が向いているので、とりあえず累積和を取る。これを数列$S$と呼ぶことにすれば、ある区間$[l,r]$について$S_r-S_l$が負、すなわち$S_l\gt S_r$であれば$[l,r]$の中央値が$X$以下であることがわかる。これをすべての区間について数えるのは$O(N{\rm log}N)$でできて、それぞれの$S_r$についてそれより前にある数字のなかで$S_r$より大きいものの数の和なので、これは転倒数と同じ考え方で数え上げることができる。ただし、累積和の最初に0を入れておくのを忘れないこと(全区間網羅したいので)。
上のようにして中央値が$X$以下の区間の数を数えたとき、それが$N(N+1)/4+1$個以上であれば、中央値の中央値は$X$以下であるとわかる。これで$X$について二分探索ができて、この問題が解けた。
難しいと思った。中央値を二分探索するテクニックは典型らしいので身に着けたい。