Добрый день, сообщество CF. Мне нужна помощь и я обращаюсь к вам за ней. Долгое время я думал, что если знаешь простые модификации на отрезке ( присвоение, прибавление, умножение с выдачей суммы, максимума, НОД, НОК и т.п. ), сжатое дерево отрезков, то проблем с модификациями на отрезке быть не должно. Но я ошибался. Проблема у меня следующая. Как осуществить присвоение, прибавление прогрессии на отрезке с выдачей максимума? Арифметической. Может ещё и сумму можно на отрезке получать после этого ( мне кажется, что наврятли ). Может ещё и с геометрической тоже можно ( на грани фантастики да и нигде такого не встречал ). Может можно ещё это делать по остатку от деления на 10^9+7 ( к примеру ) ( мне кажется, что я совсем обкурился пивом). Надеюсь, что это всё не требует персистентность или 2-3 мерные деревья. Вот задачи, которие можно решить этим методом, если он существует конечно.

http://mirror.codeforces.com/problemset/problem/396/C – HLD ( корневая декомпозиция предложаная ЗКШ у меня не зашла )

http://mirror.codeforces.com/gym/100255 задача D – сжатое ДО

Я понимаю, что можно лоб написать или корневую декомпозицию какую-нибудь. Меня интересует асимптотика log^2(n) и быстрее. Может куревом это сделать можно?