Блог пользователя jk_qq

Автор jk_qq, история, 9 лет назад, По-русски

Добрый вечер. Умеет ли кто-нибудь прибавлять прогрессию на отрезке и смотреть минимум на отрезке за logk(n), k = 1, 2? Буду очень признателен, не раз задача встречалась, до сих пор я не умею такие штуки делать.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем jk_qq (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится -16 Проголосовать: не нравится

Sorry, криво прочитал условие.

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Я не знаю другого способа это сделать, кроме как корневой декомпозицией. Разобьём массив на кусочки длины k. Будем в каждом кусочке держать сами числа, верхнюю грань выпуклой оболочки точек (i, xi) и пару чисел k, b — коэффициенты арифметической прогрессии ki + b, которую надо прибавить на этом кусочке.

Нетрудно видеть, что max(xi + ki + b) = b + max(xi + ki), под максимумом стоит скалярное произведение (xi, i) на вектор (1, k), значит мы ищем самую удалённую в некотором направлении точку из нашего множества, а такая точка всегда лежит на выпуклой оболочке. Значит, точку максимума можно найти бинарным поиском по выпуклой оболочке.

Таким образом, применяя операцию изменения, мы должны просто изменить коэффициенты k и b во всех кусочках, которые попали в запрос целиком, а на не более, чем двух кусочках, которые мы затронули частично, просто целиком перестроить всю структуру. Соответственно, чтобы спросить максимум на отрезке, его нужно поискать в кусочках, которые попали целиком, бинарным поиском, и в не более, чем двух кусочках, просто проитерировавшись по всему блоку.

Время работы получается на изменение, и на запрос. Таким образом, можно взят , и получить что-то, работающее за разумное время.

Не уверен, что это делается за .

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может кто оффлайн умеет решать, тоже было бы интересно услышать.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Помню, KADR как-то давно писал. Я тогда прочитал, проникся, поверил. Но, честно говоря, это не то, что хочется писать на контесте.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Жестко, конечно, но спасибо за ссылку:)