Дан массив A. И даны K запросов. Каждый запрос имеет вид: 1. 1 L R D: прибавить число D К отрезку L R
2. 2 L R X: Узнать количество чисел равных X на отрезке L R
.Помогите решить
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
Название |
---|
Откуда задача?
Ограничения хоть какие-то скажите. МБ там проходит тупой алгоритм))
N,K<=10^6
UPD: ошибся
У вас этот запрос тоже за log^2 работает? Если это так, то можно подробнее, как это написать?
Тяжело. Я ошибся. Почему-то показалось, что с отложенными операциями всё будет хорошо.
В принципе можно:
http://codeforces.me/blog/entry/15527#comment-204656
Но пока дальше идей дело не сдвинулось.
Боюсь, что тогда всё что можно сделать — то же самое, но теперь хранить декартовы и мёржить их каждый раз, обновив всё поддерево (увеличив в нём отрезок и пересортировав его). С ходу не скажу, насколько плохой становится асимптотика.
UPD: ясно, в чём пробема. Мы не можем мёржить, т.к. ключи левого поддерева не всегда меньше всех ключей правого. Будем вынуждены мёржить добавляя элементы по одному.
Да уж, задачка =). Похоже за log^2 не решить.
Не знаю, бред или нет: а что если как-то предподсчитать вначале, сколько раз каждая нода будет использоваться в запросах, и потом как-то хитро решать, стоит ли вызывать мердж, или просто лишний раз спуститься ниже. То есть как-то высчитывать, что быстрее можно будет выполнить (по сути еще решать задачу об оптимальном мердже =) )
Я уже спрашивал, как решать такую задачу.