An Divide and conquer algorithm with complexity O(n log n)

Question

I have two sequences of numbers (a1, a2, ... , an) and (b1, b2, ... , bn). For any i, j ∈ [n] we say (ai, bi) and (aj, bj ) agree if either ai < aj ∧ bi < bj or ai > aj ∧ bi > bj I can assume that all numbers are different.) Otherwise they disagree. Let A be the number of pairs that agree, and D be the number of pairs that disagree. Give an algorithm to compute A − D in time O(n log n).

I have no ideas how to solve it by divide and conquer algorithms. Can someone help me?

Answer 1

This problem can be reduced to the problem of counting the number of inversions in a sequence.

First, rewrite the input as if it is a single array of pairs (a₁, b₁), (a₂, b₂), ... (a_n, b_n), and then sort this sequence in ascending order of the a_i components. Since the numbers are all different, in the resulting sequence we have a_i < a_j if and only if i < j. It follows that the number D is equal to the number of inversions in the resulting sequence of b_i components, i.e. the number of pairs (i, j) where i < j and b_i < b_j. The number A is equal to n(n - 1)/2 - D, since every pair either "agrees" or "disagrees".

The inversions in that sequence can be counted in O(n log n) time using a divide-and-conquer algorithm based on merge sort, as detailed in this other Q&A.