この問題を数式で表すと「\(A_i\geq A_j\) かつ \(B_i\leq B_j\) を満たす \((i,j)\) の組は何個あるか？」 となります。( \(i\) が高橋君に渡すプレゼント、\(j\) が青木君に渡すプレゼント)

座標圧縮を行うことで、\(1\leq A_i,B_i\leq N\) であるとしてよいです。簡単のため、\((A_i,B_i)=(A_j,B_j)\) となる \((i,j)\) が存在しない場合をまず考えます。

\(i\) を \(A_i\) の昇順・タイなら \(B_i\) の降順でプレゼントを見ていくことにすると \(i\) と対になって条件を満たす \(j\) の個数は、今までに見たプレゼント(自身を含む)のうち、\(B_i\leq B_j\) を満たすものの個数になります。これはセグメントツリーを用いることで高速に求めることができます。

\((A_i,B_i)=(A_j,B_j)\) となる \((i,j)\) が存在する場合も、適切にそれらをまとめることで同様に解くことができます。

以上より \(O(N\log N)\) でこの問題が解けました。

実装例(C++)