「\(A_i \geq A_j\) かつ \(B_i \leq B_j\) を満たす \((i,j)\) の組は何個あるか？」という問題の答えは、\( (A_i,B_i) \) を \(A_i\) の昇順にソートしても変わりません。以下、 \(i \leq j \) ならば \(A_j \geq A_i\) が成り立つとします。また、公式解説と同様に座標圧縮を行い \(1 \leq A_i,B_i \leq N \) であるとします。

各 \(k (1 \leq k \leq N)\) について、\(A_k \geq A_j\) かつ \(B_k \leq B_j\) であるような \(j\) の個数が求められれば良いです。(それらを足し合わせたものが答えになるので)

\(A_i\) が単調増加することから、ある整数 \(r (1 \leq r \leq N)\) が存在し、 \(j \leq r\) であるような全ての \(j\) について \(A_k\geq A_j\) が成り立ちます。そのような \(r\) の最大値を \(r'\) とすると、\(j\) が区間 \([1, r']\) に含まれるならば、またその時に限り \(A_k\geq A_j\) が成り立ちます。 \(r'\) は二分探索を行うことにより \(O(\rm{log}\) \( N)\) で求めることが出来ます。

あとは、区間\([1,r']\) に含まれる \(j\) のうち \(2\) つ目の条件である \(B_k \leq B_j\) を満たすものの個数が求められれば良いです。これはWavelet Matrixのrangefreq関数を用いることにより \(O(\rm{log}\) \( N )\) で求められます。(Wavelet Matrixについては、Google検索を行うと複数の記事がヒットするのでそちらを参照してください)

Wavelet Matrixの構築に\(O(N\) \(\rm{log}\) \( N )\) かかり、条件を満たす \((i,j)\) の組の個数を数えるのに \(O(N\) \(\rm{log}\) \( N )\) かかるため、全体で \(O(N\) \(\rm{log}\) \( N )\) でこの問題の答えを求めることが出来ます。