Дан массив A. И даны K запросов. Каждый запрос имеет вид: 1. 1 L R D: прибавить число D К отрезку L R
2. 2 L R X: Узнать количество чисел равных X на отрезке L R
.Помогите решить
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
Название |
---|
Откуда задача?
Ограничения хоть какие-то скажите. МБ там проходит тупой алгоритм))
N,K<=10^6
UPD: ошибся
У вас этот запрос тоже за log^2 работает? Если это так, то можно подробнее, как это написать?
Тяжело. Я ошибся. Почему-то показалось, что с отложенными операциями всё будет хорошо.
В принципе можно:
http://codeforces.net/blog/entry/15527#comment-204656
Но пока дальше идей дело не сдвинулось.
Боюсь, что тогда всё что можно сделать — то же самое, но теперь хранить декартовы и мёржить их каждый раз, обновив всё поддерево (увеличив в нём отрезок и пересортировав его). С ходу не скажу, насколько плохой становится асимптотика.
UPD: ясно, в чём пробема. Мы не можем мёржить, т.к. ключи левого поддерева не всегда меньше всех ключей правого. Будем вынуждены мёржить добавляя элементы по одному.
Да уж, задачка =). Похоже за log^2 не решить.
Не знаю, бред или нет: а что если как-то предподсчитать вначале, сколько раз каждая нода будет использоваться в запросах, и потом как-то хитро решать, стоит ли вызывать мердж, или просто лишний раз спуститься ниже. То есть как-то высчитывать, что быстрее можно будет выполнить (по сути еще решать задачу об оптимальном мердже =) )
Я уже спрашивал, как решать такую задачу.