Сжатие координат

Задача просит завести массив, индексируемый значениями. Значения — до $10^9$. Массив такого размера не создать.

Но самих значений не больше $n$ — сколько дано во входных данных. Значит, важны не сами числа, а только их порядок. Заменим каждое число его номером в отсортированном списке различных — и все алгоритмы, опирающиеся на порядок, продолжат работать.

Три строки

vector<long long> sorted = a;
sort(sorted.begin(), sorted.end());
sorted.resize(unique(sorted.begin(), sorted.end()) - sorted.begin());

for (long long& value : a)
    value = lower_bound(sorted.begin(), sorted.end(), value) - sorted.begin();

После этого в a лежат числа от $0$ до $k-1$, где $k$ — количество различных значений, и для любых $i$, $j$ верно: новое $a_i$ меньше нового $a_j$ ровно тогда, когда меньше было и старое.

Проверено: на двадцати тысячах случайных массивов все попарные сравнения на «меньше» и «равно» сохранились.

Сложность — $O(n \log n)$ на сортировку и $O(n \log n)$ на бинарные поиски.

Массив sorted стоит сохранить: по нему восстанавливается исходное значение по номеру, а это почти всегда нужно для вывода ответа.

Где это нужно

Сортировка подсчётом на больших значениях. Сама сортировка тут не нужна, а вот массив счётчиков после сжатия заводится свободно.

Дерево отрезков и Фенвика по значениям. «Сколько чисел меньше $x$ уже встретилось» — стандартный запрос, требующий массива по значениям. Со сжатием он становится массивом длины $n$.

Отрезки и события. Координаты до $10^9$, а точек интереса не больше $2n$. После сжатия любая задача про «покрытие» решается массивом.

Динамика по значениям. Состояние вида «наибольшая возрастающая подпоследовательность, оканчивающаяся значением $v$» без сжатия не существует, а после — обычный массив.

Варианты

Если дубликаты нужно различать (например, при равных значениях важен исходный порядок), вместо unique сортируют пары «значение, индекс»:

vector<pair<long long, int>> pairs(n);
for (int i = 0; i < n; i++) pairs[i] = {a[i], i};
sort(pairs.begin(), pairs.end());
for (int rank = 0; rank < n; rank++) a[pairs[rank].second] = rank;

Теперь все номера различны, и равные значения получают номера в порядке появления.

Если чисел много, а разных мало, и порядок не важен вовсе, подойдёт unordered_map<long long, int> — но это медленнее из-за константы хеш-таблицы.

Про константу словаря

Отдельно стоит сказать о выборе между сортировкой и map, потому что он влияет на время сильнее, чем кажется.

map — сбалансированное дерево. Каждая операция — логарифм, но с большой константой: узлы разбросаны по памяти, каждый переход по указателю почти наверняка промах кэша.

sort — тоже $O(n \log n)$, но данные лежат подряд, и процессор читает их последовательно. На практике разница доходит до пяти-десяти раз.

Поэтому если решение уже стоит $O(n \log^2 n)$, а внутри лежит map, — это первое место, куда стоит смотреть при превышении времени. Часто достаточно заменить словарь на сжатие координат плюс обычный массив, и решение проходит без изменения асимптотики.

Общее правило: асимптотика решает, пройдёт ли решение в принципе; константа решает, пройдёт ли оно сегодня. Сжатие координат — самый дешёвый способ уменьшить константу, не трогая идею.