Добрый день, сообщество CF. Мне нужна помощь и я обращаюсь к вам за ней. Долгое время я думал, что если знаешь простые модификации на отрезке ( присвоение, прибавление, умножение с выдачей суммы, максимума, НОД, НОК и т.п. ), сжатое дерево отрезков, то проблем с модификациями на отрезке быть не должно. Но я ошибался. Проблема у меня следующая. Как осуществить присвоение, прибавление прогрессии на отрезке с выдачей максимума? Арифметической. Может ещё и сумму можно на отрезке получать после этого ( мне кажется, что наврятли ). Может ещё и с геометрической тоже можно ( на грани фантастики да и нигде такого не встречал ). Может можно ещё это делать по остатку от деления на 10^9+7 ( к примеру ) ( мне кажется, что я совсем обкурился пивом). Надеюсь, что это всё не требует персистентность или 2-3 мерные деревья. Вот задачи, которие можно решить этим методом, если он существует конечно.
http://codeforces.com/problemset/problem/396/C – HLD ( корневая декомпозиция предложаная ЗКШ у меня не зашла )
http://codeforces.com/gym/100255 задача D – сжатое ДО
Я понимаю, что можно лоб написать или корневую декомпозицию какую-нибудь. Меня интересует асимптотика log^2(n) и быстрее. Может куревом это сделать можно?
Прибавление арифм. прогрессии и выдача максимума как раз недавно обсуждалась. Стоит почитать тут.
Присвоение и максимум — думаю, проблем быть не должно. Так же как и присвоение/прибавление арифм. прогрессии и сумму — стандартная задача, решается деревом отрезков с отложенными операциями (говорим, что прибавляем прогрессию ai + b всем детям, и при пропихивании легко понять, что прибавлять левому, а что правому сыну). Прибавление геом. прогрессии — стоит почитать разбор этой задачи. Тут уж все есть :)
Спасибо большое, жаль, что для меня построение шатра — это куча кода и проблем порядка 150 строк кода. Я никогда не делал модификации в шатре, один раз только строил и запрос максимума делал и всё. Насчёт геом. прогрессии сильно удивлён, ещё и кода не много. Есть вообщем над чем подумать.
Я почти понял, как это сделать.