上位16ビットでブロックに分け, 出現数をカウントする. 出現数が \((n+1)/2\) 回以上になったブロックに中央値があるので, ここから上位16ビットを決めることができる.

上位16ビットが分かったので, この上位16ビットブロック内で下位16ビットの出現数を数えて, 同様に出現数が \((n+1)/2\) 回以上になった数値が中央値である.

想定解は二分探索のようで, 実際に最初は二分探索で提出したのだが, ギリギリTLEしてしまったのでこういう解き方にした.