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