Greetings (Codeforces 1915F)
Tags: Others, divide and conquer

There are $$$n$$$ people on the number line; the $$$i$$$-th person is at point $$$a_i$$$ and wants to go to point $$$b_i$$$. For each person, $$$a_i < b_i$$$, and the starting and ending points of all people are distinct. (That is, all of the $$$2n$$$ numbers $$$a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$$$ are distinct.) All the people will start moving simultaneously at a speed of $$$1$$$ unit per second until they reach their final point $$$b_i$$$. When two people meet at the same point, they will greet each other once. How many greetings will there be?Note that a person can still greet other people even if they have reached their final point.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of people.Then $$$n$$$ lines follow, the $$$i$$$-th of which contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$-10^9 \leq a_i < b_i \leq 10^9$$$) — the starting and ending positions of each person.For each test case, all of the $$$2n$$$ numbers $$$a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$$$ are distinct.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer denoting the number of greetings that will happen.

Note: In the first test case, the two people will meet at point $$$3$$$ and greet each other.

Sample Inputs:
5
2
2 3
1 4
6
2 6
3 9
4 5
1 8
7 10
-2 100
4
-10 10
-5 5
-12 12
-13 13
5
-4 9
-2 5
3 4
6 7
8 10
4
1 2
3 4
5 6
7 8

Sample Outputs:
1
9
6
4
0

Solution (Python):
from sys import stdin, maxsize
from math import *
input = lambda : stdin.readline().rstrip()
line = lambda s: map(s, input().split())
array = lambda s: list(line(s))

def mergeSort(lst):
    sz = len(lst)
    if sz <= 1:
        return (0, lst)
    mid = sz >> 1
    (cntl, a) = mergeSort(lst[:mid])
    (cntr, b) = mergeSort(lst[mid:])
    ans = cntl + cntr
    (szl, szr) = (len(a), len(b))
    a.append(float('inf'))
    b.append(float('inf'))
    (i, j) = (0, 0)
    res = []
    while i < szl or j < szr:
        if a[i] <= b[j]:
            ans += j
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1
    return (ans, res)

def solve():
    n = int(input())
    a = []
    for _ in range(n):
        (x, y) = line(int)
        a.append((x, y))
    a.sort(key=lambda t: (t[0], t[1]))
    lst = []
    for (x, y) in a:
        lst.append(y)
    (ans, _) = mergeSort(lst)
    print(ans)
if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

Solution (Python):
import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
from collections.abc import Sequence, MutableSequence
from functools import reduce

class SortedList(MutableSequence):
    """"""
    DEFAULT_LOAD_FACTOR = 1000

    def __init__(self, iterable=None, key=None):
        """"""
        assert key is None
        self._len = 0
        self._load = self.DEFAULT_LOAD_FACTOR
        self._lists = []
        self._maxes = []
        self._index = []
        self._offset = 0
        if iterable is not None:
            self._update(iterable)

    @property
    def key(self):
        """"""
        return None

    def _reset(self, load):
        """"""
        values = reduce(iadd, self._lists, [])
        self._clear()
        self._load = load
        self._update(values)

    def clear(self):
        """"""
        self._len = 0
        del self._lists[:]
        del self._maxes[:]
        del self._index[:]
        self._offset = 0
    _clear = clear

    def add(self, value):
        """"""
        _lists = self._lists
        _maxes = self._maxes
        if _maxes:
            pos = bisect_right(_maxes, value)
            if pos == len(_maxes):
                pos -= 1
                _lists[pos].append(value)
                _maxes[pos] = value
            else:
                insort(_lists[pos], value)
            self._expand(pos)
        else:
            _lists.append([value])
            _maxes.append(value)
        self._len += 1

    def _expand(self, pos):
        """"""
        _load = self._load
        _lists = self._lists
        _index = self._index
        if len(_lists[pos]) > _load << 1:
            _maxes = self._maxes
            _lists_pos = _lists[pos]
            half = _lists_pos[_load:]
            del _lists_pos[_load:]
            _maxes[pos] = _lists_pos[-1]
            _lists.insert(pos + 1, half)
            _maxes.insert(pos + 1, half[-1])
            del _index[:]
        elif _index:
            child = self._offset + pos
            while child:
                _index[child] += 1
                child = child - 1 >> 1
            _index[0] += 1

    def update(self, iterable):
        """"""
        _lists = self._lists
        _maxes = self._maxes
        values = sorted(iterable)
        if _maxes:
            if len(values) * 4 >= self._len:
                _lists.append(values)
                values = reduce(iadd, _lists, [])
                values.sort()
                self._clear()
            else:
                _add = self.add
                for val in values:
                    _add(val)
                return
        _load = self._load
        _lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
        _maxes.extend((sublist[-1] for sublist in _lists))
        self._len = len(values)
        del self._index[:]
    _update = update

    def __contains__(self, value):
        """"""
        _maxes = self._maxes
        if not _maxes:
            return False
        pos = bisect_left(_maxes, value)
        if pos == len(_maxes):
            return False
        _lists = self._lists
        idx = bisect_left(_lists[pos], value)
        return _lists[pos][idx] == value

    def discard(self, value):
        """"""
        _maxes = self._maxes
        if not _maxes:
            return
        pos = bisect_left(_maxes, value)
        if pos == len(_maxes):
            return
        _lists = self._lists
        idx = bisect_left(_lists[pos], value)
        if _lists[pos][idx] == value:
            self._delete(pos, idx)

    def remove(self, value):
        """"""
        _maxes = self._maxes
        if not _maxes:
            raise ValueError('{0!r} not in list'.format(value))
        pos = bisect_left(_maxes, value)
        if pos == len(_maxes):
            raise ValueError('{0!r} not in list'.format(value))
        _lists = self._lists
        idx = bisect_left(_lists[pos], value)
        if _lists[pos][idx] == value:
            self._delete(pos, idx)
        else:
            raise ValueError('{0!r} not in list'.format(value))

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _maxes = self._maxes
        _index = self._index
        _lists_pos = _lists[pos]
        del _lists_pos[idx]
        self._len -= 1
        len_lists_pos = len(_lists_pos)
        if len_lists_pos > self._load >> 1:
            _maxes[pos] = _lists_pos[-1]
            if _index:
                child = self._offset + pos
                while child > 0:
                    _index[child] -= 1
                    child = child - 1 >> 1
                _index[0] -= 1
        elif len(_lists) > 1:
            if not pos:
                pos += 1
            prev = pos - 1
            _lists[prev].extend(_lists[pos])
            _maxes[prev] = _lists[prev][-1]
            del _lists[pos]
            del _maxes[pos]
            del _index[:]
            self._expand(prev)
        elif len_lists_pos:
            _maxes[pos] = _lists_pos[-1]
        else:
            del _lists[pos]
            del _maxes[pos]
            del _index[:]

    def _loc(self, pos, idx):
        """"""
        if not pos:
            return idx
        _index = self._index
        if not _index:
            self._build_index()
        total = 0
        pos += self._offset
        while pos:
            if not pos & 1:
                total += _index[pos - 1]
            pos = pos - 1 >> 1
        return total + idx

    def _pos(self, idx):
        """"""
        if idx < 0:
            last_len = len(self._lists[-1])
            if -idx <= last_len:
                return (len(self._lists) - 1, last_len + idx)
            idx += self._len
            if idx < 0:
                raise IndexError('list index out of range')
        elif idx >= self._len:
            raise IndexError('list index out of range')
        if idx < len(self._lists[0]):
            return (0, idx)
        _index = self._index
        if not _index:
            self._build_index()
        pos = 0
        child = 1
        len_index = len(_index)
        while child < len_index:
            index_child = _index[child]
            if idx < index_child:
                pos = child
            else:
                idx -= index_child
                pos = child + 1
            child = (pos << 1) + 1
        return (pos - self._offset, idx)

    def _build_index(self):
        """"""
        row0 = list(map(len, self._lists))
        if len(row0) == 1:
            self._index[:] = row0
            self._offset = 0
            return
        head = iter(row0)
        tail = iter(head)
        row1 = list(starmap(add, zip(head, tail)))
        if len(row0) & 1:
            row1.append(row0[-1])
        if len(row1) == 1:
            self._index[:] = row1 + row0
            self._offset = 1
            return
        size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
        row1.extend(repeat(0, size - len(row1)))
        tree = [row0, row1]
        while len(tree[-1]) > 1:
            head = iter(tree[-1])
            tail = iter(head)
            row = list(starmap(add, zip(head, tail)))
            tree.append(row)
        reduce(iadd, reversed(tree), self._index)
        self._offset = size * 2 - 1

    def __delitem__(self, index):
        """"""
        if isinstance(index, slice):
            (start, stop, step) = index.indices(self._len)
            if step == 1 and start < stop:
                if start == 0 and stop == self._len:
                    return self._clear()
                elif self._len <= 8 * (stop - start):
                    values = self._getitem(slice(None, start))
                    if stop < self._len:
                        values += self._getitem(slice(stop, None))
                    self._clear()
                    return self._update(values)
            indices = range(start, stop, step)
            if step > 0:
                indices = reversed(indices)
            (_pos, _delete) = (self._pos, self._delete)
            for index in indices:
                (pos, idx) = _pos(index)
                _delete(pos, idx)
        else:
            (pos, idx) = self._pos(index)
            self._delete(pos, idx)

    def __getitem__(self, index):
        """"""
        _lists = self._lists
        if isinstance(index, slice):
            (start, stop, step) = index.indices(self._len)
            if step == 1 and start < stop:
                if start == 0 and stop == self._len:
                    return reduce(iadd, self._lists, [])
                (start_pos, start_idx) = self._pos(start)
                start_list = _lists[start_pos]
                stop_idx = start_idx + stop - start
                if len(start_list) >= stop_idx:
                    return start_list[start_idx:stop_idx]
                if stop == self._len:
                    stop_pos = len(_lists) - 1
                    stop_idx = len(_lists[stop_pos])
                else:
                    (stop_pos, stop_idx) = self._pos(stop)
                prefix = _lists[start_pos][start_idx:]
                middle = _lists[start_pos + 1:stop_pos]
                result = reduce(iadd, middle, prefix)
                result += _lists[stop_pos][:stop_idx]
                return result
            if step == -1 and start > stop:
                result = self._getitem(slice(stop + 1, start + 1))
                result.reverse()
                return result
            indices = range(start, stop, step)
            return list((self._getitem(index) for index in indices))
        else:
            if self._len:
                if index == 0:
                    return _lists[0][0]
                elif index == -1:
                    return _lists[-1][-1]
            else:
                raise IndexError('list index out of range')
            if 0 <= index < len(_lists[0]):
                return _lists[0][index]
            len_last = len(_lists[-1])
            if -len_last < index < 0:
                return _lists[-1][len_last + index]
            (pos, idx) = self._pos(index)
            return _lists[pos][idx]
    _getitem = __getitem__

    def __setitem__(self, index, value):
        """"""
        message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
        raise NotImplementedError(message)

    def __iter__(self):
        """"""
        return chain.from_iterable(self._lists)

    def __reversed__(self):
        """"""
        return chain.from_iterable(map(reversed, reversed(self._lists)))

    def reverse(self):
        """"""
        raise NotImplementedError('use ``reversed(sl)`` instead')

    def islice(self, start=None, stop=None, reverse=False):
        """"""
        _len = self._len
        if not _len:
            return iter(())
        (start, stop, _) = slice(start, stop).indices(self._len)
        if start >= stop:
            return iter(())
        _pos = self._pos
        (min_pos, min_idx) = _pos(start)
        if stop == _len:
            max_pos = len(self._lists) - 1
            max_idx = len(self._lists[-1])
        else:
            (max_pos, max_idx) = _pos(stop)
        return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

    def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
        """"""
        _lists = self._lists
        if min_pos > max_pos:
            return iter(())
        if min_pos == max_pos:
            if reverse:
                indices = reversed(range(min_idx, max_idx))
                return map(_lists[min_pos].__getitem__, indices)
            indices = range(min_idx, max_idx)
            return map(_lists[min_pos].__getitem__, indices)
        next_pos = min_pos + 1
        if next_pos == max_pos:
            if reverse:
                min_indices = range(min_idx, len(_lists[min_pos]))
                max_indices = range(max_idx)
                return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
            min_indices = range(min_idx, len(_lists[min_pos]))
            max_indices = range(max_idx)
            return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
        if reverse:
            min_indices = range(min_idx, len(_lists[min_pos]))
            sublist_indices = range(next_pos, max_pos)
            sublists = map(_lists.__getitem__, reversed(sublist_indices))
            max_indices = range(max_idx)
            return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
        min_indices = range(min_idx, len(_lists[min_pos]))
        sublist_indices = range(next_pos, max_pos)
        sublists = map(_lists.__getitem__, sublist_indices)
        max_indices = range(max_idx)
        return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

    def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
        """"""
        _maxes = self._maxes
        if not _maxes:
            return iter(())
        _lists = self._lists
        if minimum is None:
            min_pos = 0
            min_idx = 0
        elif inclusive[0]:
            min_pos = bisect_left(_maxes, minimum)
            if min_pos == len(_maxes):
                return iter(())
            min_idx = bisect_left(_lists[min_pos], minimum)
        else:
            min_pos = bisect_right(_maxes, minimum)
            if min_pos == len(_maxes):
                return iter(())
            min_idx = bisect_right(_lists[min_pos], minimum)
        if maximum is None:
            max_pos = len(_maxes) - 1
            max_idx = len(_lists[max_pos])
        elif inclusive[1]:
            max_pos = bisect_right(_maxes, maximum)
            if max_pos == len(_maxes):
                max_pos -= 1
                max_idx = len(_lists[max_pos])
            else:
                max_idx = bisect_right(_lists[max_pos], maximum)
        else:
            max_pos = bisect_left(_maxes, maximum)
            if max_pos == len(_maxes):
                max_pos -= 1
                max_idx = len(_lists[max_pos])
            else:
                max_idx = bisect_left(_lists[max_pos], maximum)
        return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

    def __len__(self):
        """"""
        return self._len

    def bisect_left(self, value):
        """"""
        _maxes = self._maxes
        if not _maxes:
            return 0
        pos = bisect_left(_maxes, value)
        if pos == len(_maxes):
            return self._len
        idx = bisect_left(self._lists[pos], value)
        return self._loc(pos, idx)

    def bisect_right(self, value):
        """"""
        _maxes = self._maxes
        if not _maxes:
            return 0
        pos = bisect_right(_maxes, value)
        if pos == len(_maxes):
            return self._len
        idx = bisect_right(self._lists[pos], value)
        return self._loc(pos, idx)
    bisect = bisect_right
    _bisect_right = bisect_right

    def count(self, value):
        """"""
        _maxes = self._maxes
        if not _maxes:
            return 0
        pos_left = bisect_left(_maxes, value)
        if pos_left == len(_maxes):
            return 0
        _lists = self._lists
        idx_left = bisect_left(_lists[pos_left], value)
        pos_right = bisect_right(_maxes, value)
        if pos_right == len(_maxes):
            return self._len - self._loc(pos_left, idx_left)
        idx_right = bisect_right(_lists[pos_right], value)
        if pos_left == pos_right:
            return idx_right - idx_left
        right = self._loc(pos_right, idx_right)
        left = self._loc(pos_left, idx_left)
        return right - left

    def copy(self):
        """"""
        return self.__class__(self)
    __copy__ = copy

    def append(self, value):
        """"""
        raise NotImplementedError('use ``sl.add(value)`` instead')

    def extend(self, values):
        """"""
        raise NotImplementedError('use ``sl.update(values)`` instead')

    def insert(self, index, value):
        """"""
        raise NotImplementedError('use ``sl.add(value)`` instead')

    def pop(self, index=-1):
        """"""
        if not self._len:
            raise IndexError('pop index out of range')
        _lists = self._lists
        if index == 0:
            val = _lists[0][0]
            self._delete(0, 0)
            return val
        if index == -1:
            pos = len(_lists) - 1
            loc = len(_lists[pos]) - 1
            val = _lists[pos][loc]
            self._delete(pos, loc)
            return val
        if 0 <= index < len(_lists[0]):
            val = _lists[0][index]
            self._delete(0, index)
            return val
        len_last = len(_lists[-1])
        if -len_last < index < 0:
            pos = len(_lists) - 1
            loc = len_last + index
            val = _lists[pos][loc]
            self._delete(pos, loc)
            return val
        (pos, idx) = self._pos(index)
        val = _lists[pos][idx]
        self._delete(pos, idx)
        return val

    def index(self, value, start=None, stop=None):
        """"""
        _len = self._len
        if not _len:
            raise ValueError('{0!r} is not in list'.format(value))
        if start is None:
            start = 0
        if start < 0:
            start += _len
        if start < 0:
            start = 0
        if stop is None:
            stop = _len
        if stop < 0:
            stop += _len
        if stop > _len:
            stop = _len
        if stop <= start:
            raise ValueError('{0!r} is not in list'.format(value))
        _maxes = self._maxes
        pos_left = bisect_left(_maxes, value)
        if pos_left == len(_maxes):
            raise ValueError('{0!r} is not in list'.format(value))
        _lists = self._lists
        idx_left = bisect_left(_lists[pos_left], value)
        if _lists[pos_left][idx_left] != value:
            raise ValueError('{0!r} is not in list'.format(value))
        stop -= 1
        left = self._loc(pos_left, idx_left)
        if start <= left:
            if left <= stop:
                return left
        else:
            right = self._bisect_right(value) - 1
            if start <= right:
                return start
        raise ValueError('{0!r} is not in list'.format(value))

    def __add__(self, other):
        """"""
        values = reduce(iadd, self._lists, [])
        values.extend(other)
        return self.__class__(values)
    __radd__ = __add__

    def __iadd__(self, other):
        """"""
        self._update(other)
        return self

    def __mul__(self, num):
        """"""
        values = reduce(iadd, self._lists, []) * num
        return self.__class__(values)
    __rmul__ = __mul__

    def __imul__(self, num):
        """"""
        values = reduce(iadd, self._lists, []) * num
        self._clear()
        self._update(values)
        return self

    def __make_cmp(seq_op, symbol, doc):
        """"""

        def comparer(self, other):
            """"""
            if not isinstance(other, Sequence):
                return NotImplemented
            self_len = self._len
            len_other = len(other)
            if self_len != len_other:
                if seq_op is eq:
                    return False
                if seq_op is ne:
                    return True
            for (alpha, beta) in zip(self, other):
                if alpha != beta:
                    return seq_op(alpha, beta)
            return seq_op(self_len, len_other)
        seq_op_name = seq_op.__name__
        comparer.__name__ = '__{0}__'.format(seq_op_name)
        doc_str = 'Return true if and only if sorted list is {0} `other`.\n \n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n \n        Comparisons use lexicographical order as with sequences.\n \n        Runtime complexity: `O(n)`\n \n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n \n        '
        comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
        return comparer
    __eq__ = __make_cmp(eq, '==', 'equal to')
    __ne__ = __make_cmp(ne, '!=', 'not equal to')
    __lt__ = __make_cmp(lt, '<', 'less than')
    __gt__ = __make_cmp(gt, '>', 'greater than')
    __le__ = __make_cmp(le, '<=', 'less than or equal to')
    __ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
    __make_cmp = staticmethod(__make_cmp)

    def __reduce__(self):
        values = reduce(iadd, self._lists, [])
        return (type(self), (values,))

    def _check(self):
        """"""
        try:
            assert self._load >= 4
            assert len(self._maxes) == len(self._lists)
            assert self._len == sum((len(sublist) for sublist in self._lists))
            for sublist in self._lists:
                for pos in range(1, len(sublist)):
                    assert sublist[pos - 1] <= sublist[pos]
            for pos in range(1, len(self._lists)):
                assert self._lists[pos - 1][-1] <= self._lists[pos][0]
            for pos in range(len(self._maxes)):
                assert self._maxes[pos] == self._lists[pos][-1]
            double = self._load << 1
            assert all((len(sublist) <= double for sublist in self._lists))
            half = self._load >> 1
            for pos in range(0, len(self._lists) - 1):
                assert len(self._lists[pos]) >= half
            if self._index:
                assert self._len == self._index[0]
                assert len(self._index) == self._offset + len(self._lists)
                for pos in range(len(self._lists)):
                    leaf = self._index[self._offset + pos]
                    assert leaf == len(self._lists[pos])
                for pos in range(self._offset):
                    child = (pos << 1) + 1
                    if child >= len(self._index):
                        assert self._index[pos] == 0
                    elif child + 1 == len(self._index):
                        assert self._index[pos] == self._index[child]
                    else:
                        child_sum = self._index[child] + self._index[child + 1]
                        assert child_sum == self._index[pos]
        except:
            traceback.print_exc(file=sys.stdout)
            print('len', self._len)
            print('load', self._load)
            print('offset', self._offset)
            print('len_index', len(self._index))
            print('index', self._index)
            print('len_maxes', len(self._maxes))
            print('maxes', self._maxes)
            print('len_lists', len(self._lists))
            print('lists', self._lists)
            raise
for _ in range(int(input())):
    n = int(input())
    l = [tuple(map(int, input().split())) for _ in range(n)]
    l.sort()
    ans = 0
    st = SortedList()
    for i in l:
        ans += len(st) - st.bisect_left(i[1])
        st.add(i[1])
    print(ans)

Solution (Python):
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound

class FenwickTree:

    def __init__(self, array):
        bit = self.bit = list(array)
        size = self.size = len(bit)
        for i in range(size):
            j = i | i + 1
            if j < size:
                bit[j] += bit[i]

    def update(self, idx, value):
        """"""
        while idx < self.size:
            self.bit[idx] += value
            idx |= idx + 1

    def prefix_sum(self, end):
        """"""
        result = 0
        while end:
            result += self.bit[end - 1]
            end &= end - 1
        return result

    def find_kth(self, k):
        """"""
        idx = -1
        for d in reversed(range(self.size.bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < self.size and self.bit[right_idx] <= k:
                idx = right_idx
                k -= self.bit[idx]
        return (idx + 1, k)

class SortedList:
    block_size = 700

    def __init__(self, iterable=()):
        self.macro = []
        self.micros = [[]]
        self.micro_size = [0]
        self.fenwick = FenwickTree([0])
        self.size = 0
        for item in iterable:
            self.insert(item)

    def insert(self, value):
        macro_idx = lower_bound(self.macro, value)
        micro_idx = upper_bound(self.micros[macro_idx], value)
        self.micros[macro_idx].insert(micro_idx, value)
        self.size += 1
        self.micro_size[macro_idx] += 1
        self.fenwick.update(macro_idx, 1)
        if len(self.micros[macro_idx]) >= self.block_size:
            half_block = self.block_size >> 1
            self.micros[macro_idx:macro_idx + 1] = (self.micros[macro_idx][:half_block], self.micros[macro_idx][half_block:])
            self.micro_size[macro_idx:macro_idx + 1] = (half_block, half_block)
            self.fenwick = FenwickTree(self.micro_size)
            self.macro.insert(macro_idx, self.micros[macro_idx + 1][0])

    def pop(self, k=-1):
        (macro_idx, micro_idx) = self._find_kth(k)
        self.size -= 1
        self.micro_size[macro_idx] -= 1
        self.fenwick.update(macro_idx, -1)
        return self.micros[macro_idx].pop(micro_idx)

    def __getitem__(self, k):
        (macro_idx, micro_idx) = self._find_kth(k)
        return self.micros[macro_idx][micro_idx]

    def count(self, value):
        return self.upper_bound(value) - self.lower_bound(value)

    def __contains__(self, value):
        return self.count(value) > 0

    def lower_bound(self, value):
        macro_idx = lower_bound(self.macro, value)
        return self.fenwick.prefix_sum(macro_idx) + lower_bound(self.micros[macro_idx], value)

    def upper_bound(self, value):
        macro_idx = upper_bound(self.macro, value)
        return self.fenwick.prefix_sum(macro_idx) + upper_bound(self.micros[macro_idx], value)

    def _find_kth(self, k):
        return self.fenwick.find_kth(k + self.size if k < 0 else k)

    def __len__(self):
        return self.size

    def __iter__(self):
        return (value for micro in self.micros for value in micro)

    def __repr__(self):
        return str(list(self))
test_cases = int(input())
for _ in range(test_cases):
    elements = int(input())
    values = []
    for _ in range(elements):
        (first, second) = input().split()
        values.append((int(first), int(second)))
    values.sort(key=lambda x: x[1])
    starts = SortedList()
    answer = 0
    for (first, second) in values:
        idx = starts.lower_bound(first)
        answer += len(starts) - idx
        starts.insert(first)
    print(answer)