Войти Регистрация
Алгоритмы

106. Лучший период роста сообщества

Сложная

delta[i] — прирост подписчиков сообщества ВКонтакте за i-й день: бывает и отрицательным, когда люди отписываются. Аналитик шлёт операции списком ops:

["set", i, x] — пересчитали i-й день, теперь прирост x;

["best", l, r] — найти непрерывный период внутри дней l..r включительно с наибольшим суммарным приростом и вернуть эту сумму. Период не пустой, хотя бы один день.

Верните список ответов на запросы best по порядку. Индексы с нуля.

В работе: Отчёт «лучшая неделя сообщества» по любому диапазону дат после правок статистики.

Пример 1

Ввод
delta = [5, -8, 3, 4, -1]
ops = [["best", 0, 4], ["set", 1, 2], ["best", 0, 4], ["best", 1, 1]]
Вывод
[7, 14, 2]

Сначала лучший период — дни 2..3 (3 + 4 = 7). После правки весь отрезок 0..3 даёт 14.

Пример 2

Ввод
delta = [-3, -1, -2]
ops = [["best", 0, 2]]
Вывод
[-1]

Все дни в минусе — берём один день с наименьшей потерей: −1.

Ограничения

  • 1 ≤ n ≤ 10⁵, 0 ≤ длина ops ≤ 10⁵
  • −10⁴ ≤ delta[i], x ≤ 10⁴
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def best_growth_period(delta, ops):
Дерево отрезковОбъединение отрезковцельO(n log n)

Источник: наша задача на данных VK. Условие пересказано своими словами.