Number of inversions in an array of pairs of integers I have a problem like this:
we have an array of elements like this :
(a0,b0)
(a1,b1)
.
.
.
(an,bn)

and I wanna find the number of elements which have one of this two condition:
1) if ai&gt;aj and bi&lt;bj then:count:=count+1
or
2) if ai&lt;aj and bi&gt;bj then:count:=count+1
I've already found an algorithm that is $O(n^2)$, but I need the  faster algorithm.
Example:
suppose we have this:
(1,5)
(4,7)
(8,2)

I wanna find the number of time that condition satisfied, so
1&lt;8 and 2&lt;5 so condition is satisfied but 1&lt;4 and 5&lt;7 so condition is
not satisfied.
You can visualize the problem like so (using a = [1,4,8], b = [5,7,2]):

As you can see, I have sorted a, with each element pointing to a position in b sorted in reverse. All we need to do now is iterate over a, counting how many previous indices were lower than us. We can can compute that with a Fenwick tree, all in $O(nlog(n))$. Here is a python implementation:
import bisect

def query(bit, i):
    ret = 0
    while i &gt; 0:
        ret += bit[i]
        i -= i &amp; -i
    return ret


def update(bit, i, delta):
    while i &lt; len(bit):
        bit[i] += delta
        i += i &amp; -i


def csFindInversions2(a, b):
    assert len(a) == len(b)

    def solve(a, b):
        tmp = sorted(b)
        lut = [
            len(b) - bisect.bisect(tmp, b[i])
            for i in sorted(range(len(a)), key=lambda i: a[i])
        ]
        bit = [0]*(len(a) + 1)
        ret = 0
        for i in lut:
            ret += query(bit, i)
            update(bit, i+1, 1)
        return ret
    return solve(a, b) + solve(b, a)

Note that this solution does not account for duplicates.