Codeforces 100971.H: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 9: | Строка 9: | ||
Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k. | Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k. | ||
Для быстрого подсчёта суммы на префиксе | Для быстрого подсчёта суммы на префиксе есть два способа: | ||
* Можно использовать дерево Фенвика или дерево отрезков с запросом суммы на отрезке и подбирать минимальный нужный префикс бинарным поиском. Сложность O(log^2(n)). | |||
* Можно использовать спуск по дереву отрезков на сумму, ища индекс k-й единицы. Сложность O(logn). | |||
[[Category: Сборник задач: Codeforces]] | [[Category: Сборник задач: Codeforces]] | ||
Текущая версия от 20:12, 8 июня 2016
Ссылка на задачу
Комментарии
Заведём массив goingToParty[], в котором будем отмечать, собирается ли прийти на вечеринку каждый из друзей.
Каждая пара (ai, bi) даёт 2 события: когда на вечеринку идут ai человек, i-й друг также приходит (goingToParty[i] = 1), а когда на вечеринку идут (bi + 1) человек, i-й друг уже не приходит (goingToParty[i] = 0).
Будем перебирать количество друзей k, приходящих на вечеринку (от 1 до n). Для фиксированного количества друзей сначала обработаем все события, связанные с количеством k, а затем требуется вывести длину минимального префикса массива goToParty[], сумма на котором равна k.
Для быстрого подсчёта суммы на префиксе есть два способа:
- Можно использовать дерево Фенвика или дерево отрезков с запросом суммы на отрезке и подбирать минимальный нужный префикс бинарным поиском. Сложность O(log^2(n)).
- Можно использовать спуск по дереву отрезков на сумму, ища индекс k-й единицы. Сложность O(logn).