Мониторинг
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special

ВКонтакте открыла второй штаб в Санкт-Петербурге! Вы не преминули возможностью сменить обстановку и решили переехать из офиса в Доме Зингера в офис на Красном мосту.

Для комфортной работы вам потребуются два монитора с одинаковой высотой, чтобы изображение на них выглядело единым целым. На складе офиса на Красном мосту есть $$$n$$$ мониторов, $$$i$$$-й из них имеет ширину $$$w_i$$$ и высоту $$$h_i$$$. Любой монитор можно повернуть на 90 градусов, и тогда он будет иметь ширину $$$h_i$$$ и высоту $$$w_i$$$.

Назовём неупорядоченную пару из двух различных мониторов подходящей, если можно их повернуть так, чтобы они имели одинаковую высоту. Любой из мониторов в паре можно как повернуть относительно исходной ориентации, так и не поворачивать.

Подсчитайте подходящие пары мониторов.

Input format:
В первой строке задано одно целое число $$$n$$$ — число мониторов на складе.

В каждой из следующих $$$n$$$ строк заданы два целых числа $$$w_i$$$ и $$$h_i$$$ ($$$1 \le w_i, h_i \le 10^9$$$) — ширина и высота $$$i$$$-го монитора. Обратите внимание, что мониторы могут быть квадратными ($$$w_i = h_i$$$), а размеры разных мониторов могут совпадать.

В этой версии задачи $$$2 \le n \le 10^5$$$.

Output format:
Выведите число подходящих пар мониторов.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
В первом примере подходящими являются пары мониторов с номерами $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(3, 4)$$$, $$$(4, 5)$$$.

Во втором примере все пары мониторов — подходящие.

Example input:
5
3 2
2 2
5 5
3 5
4 3

Example output:
5

Example input:
7
10 10
10 20
20 10
10 20
10 20
10 10
20 10

Example output:
21

Editorial:
Опишем два подхода к эффективному решению задачи.
Первый подход — «онлайновый». Будем обрабатывать мониторы по одному. Научимся для монитора $$$j$$$ считать, со сколькими предыдущими он образует подходящую пару.
Если $$$j$$$-й монитор квадратный ($$$w_j = h_j$$$), подходят мониторы, у которых хотя бы одно измерение равно $$$w_j$$$.
В противном случае ($$$w_j \ne h_j$$$) подходят мониторы, у которых хотя бы одно измерение равно $$$w_j$$$, и мониторы, у которых хотя бы одно измерение равно $$$h_j$$$. Но если мы сложим мониторы первого и второго типа по отдельности, то мониторы, у которых есть и измерение $$$w_j$$$, и измерение $$$h_j$$$ (иначе говоря — мониторы с такими же измерениями, как и текущий), окажутся посчитаны дважды — число таких мониторов нужно вычесть.
Будем поддерживать два массива: первый будет считать мониторы с заданным измерением, а второй — с заданной парой измерений. Поскольку измерения могут принимать значения до $$$10^9$$$, массивы нужны ассоциативные: например, std::map или std::unordered_map в C++, TreeMap или HashMap в Java, dict в Python. В зависимости от используемой структуры данных сложность решения составит $$$O(n)$$$ или $$$O(n \log n)$$$.
Пример решения на C++:
Второй подход — «оффлайновый». Запишем в один обычный массив измерения всех мониторов (длины сторон квадратных мониторов запишем только один раз) и подсчитаем в этом массиве число пар одинаковых элементов. Любая такая пара соответствует подходящей паре мониторов.
При этом, аналогично предыдущему решению, пары неквадратных мониторов с обоими одинаковыми измерениями окажутся посчитаны дважды. Чтобы это исправить, запишем в другой массив все пары измерений неквадратных мониторов, и число пар одинаковых пар в этом массиве вычтем из ответа.
Подсчитать число пар одинаковых элементов в массиве можно с помощью сортировки и линейного прохода. Сложность решения составит $$$O(n \log n)$$$.
Пример решения на Python:
Наиболее часто возникавшие у участников проблемы при решении задачи:
• Максимальный возможный ответ равен $$$C(10^5, 2) = 4\,999\,950\,000$$$ — это число не помещается в 32-битный целочисленный тип.
• Некоторые решения хорошо работают на случайных тестах, но всё ещё имеют сложность $$$O(n^2)$$$ в худшем случае. Например, можно в первом решении в массиве solo хранить не число мониторов, а список их индексов, и к ответу прибавлять размер объединения списков solo[w] и solo[h]. Такой подход сработает, если подходящих пар мониторов не слишком много, но окажется неэффективным, если у всех мониторов одинаковая высота.