Добрый вечер. Умеет ли кто-нибудь прибавлять прогрессию на отрезке и смотреть минимум на отрезке за logk(n), k = 1, 2? Буду очень признателен, не раз задача встречалась, до сих пор я не умею такие штуки делать.
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Добрый вечер. Умеет ли кто-нибудь прибавлять прогрессию на отрезке и смотреть минимум на отрезке за logk(n), k = 1, 2? Буду очень признателен, не раз задача встречалась, до сих пор я не умею такие штуки делать.
Название |
---|
Автокомментарий: текст был обновлен пользователем jk_qq (предыдущая версия, новая версия, сравнить).
Sorry, криво прочитал условие.
речь идёт про запрос минимума на отрезке, а не про сумму.
А минимум?
Я не знаю другого способа это сделать, кроме как корневой декомпозицией. Разобьём массив на кусочки длины k. Будем в каждом кусочке держать сами числа, верхнюю грань выпуклой оболочки точек (i, xi) и пару чисел k, b — коэффициенты арифметической прогрессии ki + b, которую надо прибавить на этом кусочке.
Нетрудно видеть, что max(xi + ki + b) = b + max(xi + ki), под максимумом стоит скалярное произведение (xi, i) на вектор (1, k), значит мы ищем самую удалённую в некотором направлении точку из нашего множества, а такая точка всегда лежит на выпуклой оболочке. Значит, точку максимума можно найти бинарным поиском по выпуклой оболочке.
Таким образом, применяя операцию изменения, мы должны просто изменить коэффициенты k и b во всех кусочках, которые попали в запрос целиком, а на не более, чем двух кусочках, которые мы затронули частично, просто целиком перестроить всю структуру. Соответственно, чтобы спросить максимум на отрезке, его нужно поискать в кусочках, которые попали целиком, бинарным поиском, и в не более, чем двух кусочках, просто проитерировавшись по всему блоку.
Время работы получается на изменение, и на запрос. Таким образом, можно взят , и получить что-то, работающее за разумное время.
Не уверен, что это делается за .
Может кто оффлайн умеет решать, тоже было бы интересно услышать.
Помню, KADR как-то давно писал. Я тогда прочитал, проникся, поверил. Но, честно говоря, это не то, что хочется писать на контесте.
Жестко, конечно, но спасибо за ссылку:)