Read problems statements in [Hindi], [Mandarin Chinese], [Vietnamese], and [Bengali] as well.

You are given two sets of segments on a line, $A$ and $B$. Set $A$ contains $N$ segments (numbered $1$ through $N$); for each valid $i$, the $i$-th of these segments is $S_{A,i} = [L_{A,i}, R_{A,i}]$. Set $B$ contains $M$ segments (numbered $1$ through $M$); for each valid $i$, the $i$-th of these segments is $S_{B,i} = [L_{B,i}, R_{B,i}]$. 

Find $\sum_{i=1}^N \sum_{j=1}^M |S_{A,i} \cap S_{B,j}|$, where $|S_{A,i} \cap S_{B,j}|$ denotes the length of the intersection of the $i$-th segment from set $A$ and the $j$-th segment from set $B$. Note that the length of a segment $[l, r]$ is $r-l$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $L_{A,i}$ and $R_{A,i}$.
$M$ more lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $L_{B,i}$ and $R_{B,i}$.

------  Output ------
For each test case, print a single line containing one integer ― the value of the sum.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 10^{5}$
$1 ≤ L_{A,i} < R_{A,i} ≤ 10^{8}$ for each valid $i$
$1 ≤ L_{B,i} < R_{B,i} ≤ 10^{8}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$
the sum of $M$ over all test cases does not exceed $2 \cdot 10^{5}$

------  Example Input ------

3
2 2
1 2
3 4
1 3
2 4
1 1
1 2
3 4
2 1
5 6
6 8
5 8

------  Example Output ------

2
0
3

------  Explanation ------
Example case 1: The intersection of $S_{A,1}$ and $S_{B,1}$ is the segment $[1, 2]$. The intersection of $S_{A,2}$ and $S_{B,2}$ is $[3, 4]$. Both remaining intersections have lengths $0$, so the sum is $1 + 1 = 2$.

Example case 2: The only two segments have an empty intersection, which has length $0$.

Example case 3: The segment $[5, 8]$ is covered by both sets of segments, so the sum is $3$.

Difficulty: VERY_HARD
Tags: Sweep line algorithms

Range queries
Skill types: Range queries

Starter code:

Solutions:
from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(l1, l2) = ([], [])
	for _ in range(n):
		(a, b) = map(int, input().split())
		l1.append((a, 1))
		l1.append((b, 2))
	for _ in range(m):
		(a, b) = map(int, input().split())
		l1.append((a, 3))
		l1.append((b, 4))
	l1.sort()
	ans = 0
	(a, b, prev) = (0, 0, 0)
	for (i, e) in enumerate(l1):
		ans += a * b * (e[0] - prev)
		if e[1] == 1:
			a += 1
		elif e[1] == 2:
			a -= 1
		elif e[1] == 3:
			b += 1
		else:
			b -= 1
		prev = e[0]
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
(tc,) = inp()
for _ in range(tc):
	(n, m) = inp()
	a = [inp() for i in range(n)]
	b = [inp() for i in range(m)]
	A = [i for (i, j) in a] + [j for (i, j) in a]
	B = [i for (i, j) in b] + [j for (i, j) in b]
	A.sort()
	B.sort()
	c = [0]
	N = len(A)
	M = len(B)
	i = j = 0
	IND = {}
	while i < N and j < M:
		if A[i] <= B[j]:
			if c[-1] != A[i]:
				c.append(A[i])
			i += 1
		else:
			if c[-1] != B[j]:
				c.append(B[j])
			j += 1
	while i < N:
		if c[-1] != A[i]:
			c.append(A[i])
		i += 1
	while j < M:
		if c[-1] != B[j]:
			c.append(B[j])
		j += 1
	d = c.copy()
	for (i, val) in enumerate(c):
		IND[val] = i
	C = [0] * len(c)
	D = [0] * len(d)
	for (i, j) in a:
		C[IND[i]] += 1
		C[IND[j]] -= 1
	for (i, j) in b:
		D[IND[i]] += 1
		D[IND[j]] -= 1
	for i in range(1, len(c)):
		C[i] += C[i - 1]
		D[i] += D[i - 1]
	ans = 0
	for i in range(len(c) - 1):
		ans += C[i] * D[i] * (c[i + 1] - c[i])
	print(ans)


rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
yn = lambda x: print('Yes') if x else print('No')
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
from bisect import bisect_left
for _ in range(rn()):
	(n, m) = rns()
	a = []
	for i in range(n):
		a.append(rl())
	acc = []
	for i in range(n):
		acc.append([a[i][0], 1])
		acc.append([a[i][1], 0])
	acc.sort()
	indexes = [i[0] for i in acc]
	pre = []
	lines = []
	curr = 0
	ones = 0
	for i in range(len(acc) - 1):
		pre.append(curr)
		lines.append(ones)
		if acc[i][1] == 1:
			ones += 1
		else:
			ones -= 1
		curr += ones * (acc[i + 1][0] - acc[i][0])
	pre.append(curr)
	lines.append(ones)
	b = []
	for i in range(m):
		b.append(rl())
	ans = 0
	for entry in b:
		left = 0
		i = bisect_left(indexes, entry[0])
		if i == len(indexes):
			left = pre[-1]
		else:
			if i > 0 and indexes[i] != entry[0]:
				i -= 1
			left = pre[i] + max(entry[0] - indexes[i], 0) * lines[min(i + 1, len(lines) - 1)]
		j = bisect_left(indexes, entry[1])
		right = 0
		if j == len(indexes):
			right = pre[-1]
		else:
			if j > 0 and indexes[j] != entry[1]:
				j -= 1
			right = pre[j] + max(entry[1] - indexes[j], 0) * lines[min(j + 1, len(lines) - 1)]
		ans += right - left
	print(ans)