Че-то никак мысли не приходят, вроде простая задача должна быть, на форуме написано, что решается множеством способов. Может кто-нибудь подробно написать решение?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
И она используется при изучении следующих тем:
- sqrt-декомпозиция
- дерево Фенвика
- дерево отрезков
- декартово дерево
Отсортируем все точки по координате X, при равенстве X - по Y. Очевидно что в получившейся последовательности для некоторой позиции i, все точки имеющие позиции большие чем i находятся либо правее либо выше (с учетом того, что двух одинаковых точек быть не может). Причем все точки которые имеют позиции меньшие чем i находятся не правее. Т.е задача свелась к тому, что нужно для каждой точки определять сколько точек из тех, что находятся в отсортированной последовательности левее данной, находятся не выше.
Для этого сделаем следующее:
Заведем нитервальное дерево для суммы, изначально пустое. Будем идти по отсортированным точкам. Level текущей точки будет сумма в дереве от 0 до Y текущей точки. После того, как мы узнали Level текущей точки, нужно увеличить элемент с номером Y текущей точки на единицу.
Вот так будет работаеть тест из примера:
изначально есть:(1 1), (5 1), (7 1), (3 3), (5 5)
после сортирования:
(1 1), (3 3), (5 1), (5 5), (7 1)
Собираем решение:
итерация 1.
дерево сумм[0.. maxY]: 0 0 0 0 0 0
ответ [0.. n - 1]: 0 0 0 0 0
позиция 0:
Берем в дереве сумму с 0 по 1, она равна 0. в ответ добавляем одну точку 0 уровня. В дереве увеличиваем элемент [1] на единицу.
итерация 2.
дерево сумм[0.. maxY]: 0 1 0 0 0 0
ответ [0.. n - 1]: 1 0 0 0 0
позиция 1:
Берем в дереве сумму с 0 по 3, она равна 1. в ответ добавляем одну точку 1 уровня. В дереве увеличиваем элемент [3] на единицу.
итерация 3.
дерево сумм[0.. maxY]: 0 1 0 1 0 0
ответ [0.. n - 1]: 1 1 0 0 0
позиция 2:
Берем в дереве сумму с 0 по 1, она равна 1. в ответ добавляем одну точку 1 уровня. В дереве увеличиваем элемент [1] на единицу.
итерация 4.
дерево сумм[0.. maxY]: 0 2 0 1 0 0
ответ [0.. n - 1]: 1 2 0 0 0
позиция 3:
Берем в дереве сумму с 0 по 5, она равна 3. в ответ добавляем одну точку 3 уровня. В дереве увеличиваем элемент [5] на единицу.
итерация 5.
дерево сумм[0.. maxY]: 0 2 0 1 0 1
ответ [0.. n - 1]: 1 2 0 1 0
позиция 4:
Берем в дереве сумму с 0 по 1, она равна 2. в ответ добавляем одну точку 2 уровня. В дереве увеличиваем элемент [1] на единицу.
дерево сумм[0.. maxY]: 0 3 0 1 0 1
конечный ответ [0.. n - 1]: 1 2 1 1 0
Вот так мы получили ответ. Для того, чтобы посмотреть как строить дерево для сумм, можно почитать на вики статю про RSQ, или дерево Фенвика. Запросы взять сумму и обновить элемент дерева будут работать за log(maxY), всего такиз запросов нужно будет выполнить N. Итого вычислительная сложность порядка Nlog(N)
Не туда :(
сложность o(n*sqrt(n)*log(maxy))
Может можно как-нибуть по-другому?
Напишите пожалуйста!
всё гораздо проще, если отвечать на входные данные сразу. ( онлайн )
так как входные данные подаются по отсортированному Y, то можно его вообще отбросить, так как роли он никакой не играет.
в итоге задача свелась к нахождению количества чисел находящихся не правее данного.
и теперь можно делать sqrt-декомпозицию только для [0;32000], а не [0;32000]*[0;32000]. =)
Вспомнил тот прикол, что когда я стал соадмином одного АСМ-сайта, и начал иногда из интереса читать коды знакомых по некоторым задачам, то сразу нашел штук 10 задач, где кривые тесты и проходит явный бред:)
Хотя иногда полезно бывает "не умничать" и придумать простенькое решение.
А эту задачу с тимуса я тоже sqrt-декомпозицией делал.