Здравствуй КФ! Давно хотел узнать, как можно решить такую задачу : 1. Дан массив a[] из n элементов 2. Есть Q запросов : a) L, R, Value : Со всеми элементами массива на отрезке [L .. R] сделать следующее : mas[i] = max(mas[i], Value) b) L, R Вывести сумму элементов на отрезке [L .. R]
Давайте обсудим варианты решения :)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 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 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Какие ограничения? Числа до 10^9?
1 <= n <= 3 * 10^5 1 <= q <= 3 * 10^5 1 <= mas[i] <= 2 * 10 ^ 9
Неправильное решение
/
По-моему не получится, как вы будете мёрджить 2 дерева по явному ключу, если у них значения в левом не всегда меньше, чем в правом?
Почему не меньше?
Мы расспилитили дерево на <=value и >value. Потом присвоили левому value. Получили два дерева =value и >value. Вроде все ок...
Я про декартовы деревья, которые хранятся в каждой вершине.
Допустим, пришёл запрос в корень "убрать все меньше 2", вы их убрали из treap[1], как-то даже может быть протолкнули дальше. После этого запрос "убрать все, меньшие 5" для правого поддерева (treap[3]), оттуда тоже как-то убрали. Теперь надо что-то сделать с treap[1], у него элементы в рандомных позициях стали равны 5. Смёрджить treap[2] и treap[1] не получится.
Согласен, бред сказал(
Будем хранить в каждой вершине ДО отсортированный по убыванию список чисел, которые эта вершина контролирует. Когда приходит запрос на обновление делаем следующее: находим те вершины, которые полностью находятся внутри диапазона на обновление (минимальное множество) и начинаем выкидывать числа из списка, которые меньше заданного числа обновления. Как только мы закончим ответом для данной вершины будет сумма чисел в списке + последнее число в списке оставшееся количество раз (сколько нужно) + обновляем если необходимо число, которое нужно пушить вниз (на самом деле это просто будет последнее число в списке).
Получается каждое число будет в ДО не более чем в
log(n)вершинах и столько же раз может удалиться. Итоговая ассимптотикаO((n + q)log(n).Здесь не будет той же проблемы? Пусть из корня выпилили все, меньшие 3, дальше всегда это будем проталкивать. Потом откуда-то из глубокого места убрали все, меньшие 5, допустим правильно передали сумму наверх. Теперь вписок в корне содержит элементы, которых уже нет. Теперь из корня опять что-то удалили, как вы будете обновлять сумму в корне дерева?
Тут придется хранить число и указатель на ячейку для этого числа (не значение этого числа, а номер запроса, для запросов с одинаковым значением), указывающее выпилили ли мы это число или нет. Когда мы из вершины удалили число, мы указатель в этой вершине пометили, что оно мертвое. Теперь сумму в предках посчитаем верно, но когда начнем выпиливать, то корректно выпилим. То есть выпилим все что меньше значения, затем все мертвые на хвосте. Как то так.
Я не понял, как мы в корне узнаем, что где-то глубоко удалилось какое-то число (чтобы в корне пометить, что оно мёртвое).
Допустим в вершине, где-то глубоко удалилось какое-то число, мы храним не только значение этого числа, но и дополнительный индекс. Мы пометили что этот индекс мертвый. Допустим мы изменили текущую вершину удалив эту пару (значение, индекс), вверх мы передали корректную сумму + еще можно передать кол-во чисел живых. Теперь до корня дойдет следующая информация корректная сумма + кол-во живых значений. В корне у нас есть корректная информация на счет суммы + список, в котором есть лишние значения, НО их индексы помечены как мертвые. Теперь происходит изменение в корне, мы начинаем что-то удалять, удаляем не только то, что меньше числа, которым обновляем, но и все хвостовые мертвые значения. Для того, чтобы в конце находилось корректное число, которое мы вскоре будем пушить. При удалении мы подсчитаем сколько живых вершин мы выбросили, откуда следует, что мы можем знать кол-во живых вершин, откуда узнаем сколько раз последнее живое число в сумму нужно добавить.
Да, действительно, спасибо.