二分探索において判定問題を考えるという方針は同じですが、素朴な式変形でも解けます。

濃度が \(x\) 以上になる組み合わせを数え上げることを考えます。まず、濃度が \(x\) 以上であることは \(\frac{A+C}{A+B+C+D} \geq x\) と同値です。

両辺に \(A+B+C+D\) をかけて式変形をすることで \(\left( C+D \right) x- C \leq A - \left( A+B \right) x\) を得ます。

よって、 \(\left( C+D \right) x- C\) からなる ( sort された ) 配列を二分探索の度に作成することで \(\left( A,B \right)\) ごとに条件を満たす \(\left( C,D \right)\) の個数を lower_bound など二分探索で求めることができます。

これより、判定問題を \(O \left( \left( N+M \right) \log M \right)\) で解くことができました。