Место в каталоге
Сейсмологическая служба сопровождает каждое новое землетрясение строчкой «это k-е по силе землетрясение с начала наблюдений». Каталог растёт событие за событием, и для каждого нового события нужно знать, сколько прежних были строго сильнее него: место нового события равно этому числу плюс один. Землетрясения одинаковой силы друг друга не опережают.
Один из тестов — все землетрясения силой от 5 с 2015 по 2025 год из каталога USGS в порядке времени, 19 073 события; магнитуда умножена на 100.
Вход
В первой строке n (1 ≤ n ≤ 100 000). Во второй — n целых чисел a1, …, an (|ai| ≤ 10⁹) — сила событий в порядке времени.
Выход
n строк: в i-й — число 1 + |{j < i : aj > ai}|.
Примеры
Пример 1
7 510 536 550 540 540 610 500
1 1 1 2 2 1 7
Пример 2
6 7 7 3 9 7 3
1 1 3 1 2 5
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебор всех прежних событий для каждого нового — это n²/2 сравнений, пять миллиардов при ста тысячах событий. Что нужно помнить о прежних событиях, чтобы отвечать быстрее?
2Подсказка 2
Достаточно счётчиков: сколько прежних событий имели каждую силу. Тогда ответ — сумма счётчиков всех сил больше данной. Сумма на отрезке с изменениями по одному — работа для дерева Фенвика. Но силы бывают до миллиарда.
3Идея
Сначала сжимаем значения: сортируем разные силы по убыванию и нумеруем с единицы. Теперь «сильнее» — значит «с меньшим номером», и число прежних более сильных событий — сумма счётчиков с номерами от 1 до номер − 1, то есть сумма префикса. Идём по событиям: спрашиваем сумму префикса, печатаем её плюс один, прибавляем единицу к счётчику своего номера.
4Разбор
Сжатие — словарь «значение → номер» после сортировки в Python и двоичный поиск по отсортированному срезу в Go. Дерево Фенвика хранит k + 1 чисел, где k — число разных сил; сумма префикса снимает младшую единицу номера, прибавление её прибавляет.
Равные силы обрабатываются сами собой: событие той же силы получает тот же номер и в сумму префикса до номер − 1 не входит. Если бы нужно было считать «не слабее», префикс брался бы до своего номера включительно.
Можно обойтись и без дерева: держать прежние силы в отсортированном списке и вставлять каждую новую двоичным поиском (bisect.insort). Ответ — сколько элементов списка правее места вставки. Вставка сдвигает хвост списка, O(n), но это один быстрый сдвиг памяти на C, и при ста тысячах событий такое решение укладывается в ограничения; на миллионах событий сдвиги проиграли бы дереву во много раз.
4+Решение
5Сложность
Сортировка — O(n log n), каждое событие — две операции с деревом по O(log k). Итого O(n log n) времени и O(n) памяти.
6Типичные ошибки
- Перебор прежних событий. Верно, но O(n²): в пятом и шестом тестах по 30 000 событий подряд по убыванию и по возрастанию, в четвёртом — сто тысяч.
- Дерево по самим значениям. Массив на два миллиарда счётчиков не поместится в память; значения нужно сжать.
- Нестрогое сравнение. Событие той же силы не сильнее: во втором примере третья семёрка стоит на втором месте, а не на четвёртом.
- Сжатие по возрастанию без переворота. Тогда сумма префикса считает более слабые события; нужно либо нумеровать по убыванию, либо брать разность: все прежние минус не более сильные.