Расскажите, plz, как решаются задачи E и G
UPD. Спасибо за содержательные ответы.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 164 |
| 2 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | nor | 155 |
| 6 | maroonrk | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Пусть bi - кол-во чисел из a, которые не меньше i (1 ≤ i ≤ n). Для того, чтобы перестановка существовала, должно выполняться: bn ≥ 1, bn - 1 ≥ 2, ... bi ≥ n + 1 - i, ... b1 ≥ n. Для проверки этого я хранил в дереве отрезков для минимума числа bi - (n + 1 - i). Теперь, если в данный момент минимум на всём массиве меньше 0, то ответ NIE, иначе ответ TAK. Когда приходит запрос изменения числа x на y, если x < y, то надо прибавить 1 ко всем числам отрезка [x + 1, y], если x > y, то надо отнять 1 от всех чисел отрезка [y + 1, x].
Но мне почему-то кажется, что существует решение проще.
Е:
Решаем в оффлайне. Строим все дерево из работников. Для каждого уровня нужно упорядочить работников. Можно просто запустить DFS для каждого работника запоминаем время входа и выхода. И упорядочивасть согласно времени входа. Время выхода тоже понадобится :)
Для каждого уровня строится свое дерево отрезков, которые умеет считать сумму на отрезке.
Далее идем по запросам и обрабатываем их. Если добавление работника, то в дерево отрезков для данного уровня увеличиваем значение соответствующее данному работнику.
Если нужно посчитать кол-во работников на некотором уровне ниже от работника i. То мы знаем что эти работники в дереве находятся на некотором уровне h. Для этого уровня h у нас есть дерево отрезков и в нем как раз нужно посчитать сумму. Но нужно не общее кол-во добавленных, а только в поддерево, т.е. на самом деле только те работники, у которых время входа больше, чем время входа работника i, и в то же время меньше времени выхода работника i. Т.е. можно для каждого уровня хранить времена входов всех работников, и там двумя бинарными поисками, найти отрезок для которого нам надо посчитать сумму в дерево отрезков :)
Надеюсь более или менее понятно :)
Интересно как решается задача I есть какие-нибудь идеи ?
A* ?
требуется их разбить на три множества A, B, C
так чтобы S(A) <= S(B) <= S(C) и S(C) - S(A) минимально.
вывести S(C) - S(A). S(x) - сумма элементов в множестве.