Read problems statements in Mandarin Chinese and Russian as well. 
Today is the reunion of all chefs in the world. Our Chef wants to make this moment more happier. He arranged a mass wedding in this reunion. For this, he made a strange stage and drew two horizontal parallel lines on the stage. There are N unmarried male chefs in the reunion and he gave each male chef i an unique number M_{i}. Then all male chefs will stand in the first line drawn by Chef. But they will stand in increasing order of their number. That means chef with the lowest number will stand at the leftmost position of the line, then right to him would be the chef with the second lowest number and so on. Similarly, there are N female chefs in the reunion and Chef also gave each female chef j an unique number F_{j} (sequences F_{j} and M_{i} can have equal numbers). Then all female chefs will stand in the other line following the same rule(will stand in increasing order of the numbers) as the male chef. 
Now chef will choose all the marriage pairs himself. He will select a female chef and a male chef (both of them have not selected before) and will draw a straight line between them. He calls this line a marriage line. He will do this for the rest of the chefs. 
You will be given the N marriage lines; you have to find how many marriage line pairs intersect with each other.

------ Input ------ 

First line contains a single integer N. The i-th line of the next N lines contain two space separated integers M_{i} and F_{i}, means there is a marriage line between male chef M_{i} and female chef F_{i}. No marriage line will be mentioned twice.

------ Output ------ 

Output the number of marriage line pairs that intersect with each other on a single line.

------ Constraints ------ 

$1 ≤ N ≤ 100000 (10^{5})$
$0 ≤ M_{i}, F_{i} ≤ 1000000000 (10^{9})$
 
----- Sample Input 1 ------ 
3
2 3
3 6
5 4
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
Example case 1. Only marriage lines (3, 6) and (5, 4) intersect with each other.

----- Sample Input 2 ------ 
4
5 12
10 11
11 9
30 1
----- Sample Output 2 ------ 
6
----- explanation 2 ------ 
Example case 2. All the marriage lines intersect with each other.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
from bisect import bisect_left

def solve(arr):
	arr = sorted(arr, key=lambda x: x[0])
	nums = []
	ans = 0
	for (x, y) in arr:
		idx = bisect_left(nums, y)
		if idx == len(nums):
			nums.append(y)
		else:
			ans += len(nums) - idx
			nums.insert(idx, y)
	return ans
arr = []
for i in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	arr.append((x, y))
print(solve(arr))


def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def getsum2(BITTree, l, r):
	return getsum(BITTree, r) - getsum(BITTree, l - 1)
n = int(input())
females = []
males = []
all_ = []
for _ in range(n):
	(a, b) = map(int, input().split())
	females.append(b)
	males.append(a)
	all_.append((a, b))
males.sort()
females.sort()
m = {}
f = {}
for i in range(n):
	m[males[i]] = i + 1
	f[females[i]] = i + 1
line = {}
for i in range(n):
	x = m[all_[i][0]]
	y = f[all_[i][1]]
	line[x] = y
ans = 0
bit = [0] * (100000 + 2)
bit = construct(bit, 100000 + 2)
for i in range(n, 0, -1):
	x = line[i]
	ans += getsum(bit, x)
	updatebit(bit, 100000 + 2, x, 1)
print(ans)


def find(arr, n, ele):
	l = 0
	r = n - 1
	mid = (l + r) // 2
	while l != r:
		cur_ele = arr[mid]
		if cur_ele == ele:
			break
		elif cur_ele > ele:
			r = mid - 1
			mid = (l + r) // 2
		else:
			l = mid + 1
			mid = (l + r) // 2
	return mid

def pr_sum(bit, n, index):
	ans = 0
	while index:
		ans += bit[index]
		index -= index & -index
	return ans

def update(bit, n, index):
	while index <= n:
		bit[index] += 1
		index += index & -index
	return bit
n = int(input())
lst = [0] * n
for i in range(n):
	a = list(map(int, input().split()))
	lst[i] = a
lst.sort(key=lambda x: x[0])
f = [0] * n
i = 0
for pair in lst:
	f[i] = pair[1]
	i += 1
array = f
n = len(array)
sr_arr = sorted(array)
in_arr = [0] * n
i = 0
for ele in array:
	index = find(sr_arr, n, ele)
	in_arr[i] = index + 1
	i += 1
bit = [0] * (n + 1)
inv_cnt = 0
for ele in reversed(in_arr):
	inv_cnt += pr_sum(bit, n, ele)
	bit = update(bit, n, ele)
print(inv_cnt)


def mergeSort(arr, left, right):
	if right > left:
		mid = (left + right) // 2
		a = mergeSort(arr, left, mid)
		b = mergeSort(arr, mid + 1, right)
		c = merge(arr, left, mid, right)
		return a + b + c
	return 0

def merge(arr, left, mid, right):
	n1 = mid - left + 1
	n2 = right - mid
	newarr = [0] * (right - left + 1)
	i = left
	j = mid + 1
	k = 0
	inversions = 0
	while i <= mid and j <= right:
		if arr[i] < arr[j]:
			newarr[k] = arr[i]
			i += 1
		else:
			inversions += mid - i + 1
			newarr[k] = arr[j]
			j += 1
		k += 1
	while i <= mid:
		newarr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		newarr[k] = arr[j]
		k += 1
		j += 1
	for i in range(len(newarr)):
		arr[left + i] = newarr[i]
	return inversions
n = int(input())
arr = []
for _ in range(n):
	(a, b) = [int(c) for c in input().split()]
	arr.append((a, b))
arr.sort(key=lambda x: x[0])
ar = [j for (i, j) in arr]
print(mergeSort(ar, 0, len(ar) - 1))