ABC155 D. Pairs

問題

N個の整数A_iが与えられる。
このうち、2つを選んだ積の組合せをすべて考えると、これはN*(N-1)/2個できる。
小さい方からK番目の積が何になるか答えよ。

制約

• 2 <= N <= 2*10^5
• 1 <= K <= N*(N-1)/2
• -10^9 <= A_i <= 10^9

解法

積を小さい方から並べた数列Bを考える。(これは実際には列挙できない)
Bのうち、「x未満の個数」が高速に求められれば、K番目の要素は、「x未満の個数がK未満」の部分を二分探索すれば求められる。

例えば、Bが「1,2,4,4」の場合、「x未満の個数」をmとすると、

x 1 2 3 4 5
m 0 1 2 2 4

のようになるので、K=3だった場合は、xが4と5のところで分かれるので3番目に来るのは「4」だとわかる。(K=4でも、K未満となる位置は同じなので、答えが「4」であることがわかる。)

したがって、Bにおける「x未満の個数」を高速に求めれば良い。

今回、A_iは0や負もあり得るため、その積はやや複雑になっている。
正だけだった場合は、A_iを小さい順からソートして、二分探索でx未満となる位置を求めて個数を計算すれば、O(N*log(N))で求められる。
しかし、今回は負もあるため、負*負や負*正の時を気をつける必要がある。

実装的には、A_iを「①0未満のもの」と「②0以上のもの」と分けて、
①*①と①*②と②*②それぞれで個数を求めて合計してあげればよい。

(①*①のときは、負*負になるため、逆順にソートして上げると順方向の二分探索ができる。
①*②のときは、負*正になるため、②側のものを逆順にソートしてあげると順方向の二分探索にできる。
②*②のときは、正*正なので、そのまま二分探索してあげれば良い。)