Невозможно решить проблему codechef

Question

Достаточно ли (O (n), O (log n)) подхода для решения проблемы - http://www.codechef.com/problems/MULTQ3/?

(Время обновления - O (n), время запроса - O (log n))

Мое решение - решение с использованием вышеуказанного подхода (с использованием деревьев сегментов) было признано судьей Codechef отправкой «TLE».

Ну, я даже попробовал (O (log n), O (n)) подход к проблеме (время обновления - O (log n), время запроса - O (n)), но даже это было отклонено судья Codechef как превышающий срок. Я понятия не имею, куда идти отсюда. Вот ссылка на мою вторую заявку - http://www.codechef.com/viewsolution/558614

Любого, кто уже решил проблему, просят помочь мне в этом. Могу ли я сделать это (O (lgn) -O (lgn))? как?

Заранее спасибо.

Answer 1

Это действительно можно сделать O(log(n)), O(log(n)).

Хитрость заключается в том, чтобы дерево представляло собой структуру данных со следующими частями информации на каждом узле:

• startиндекс
• конечный индекс
• левый узел
• правый узел
• сколько 0 мод (3)
• сколько 1 мод (3)
• Сколько 2 мода (3)
• Сумма не примененного обновления

Когда вам говорят, что нужно применить обновление, вам нужно только применить его (и этонеприменимое количество) к узлам, имеющим границу внутри этого диапазона.В противном случае просто увеличьте количество непримененных обновлений.Вы будете лениво применять его, если вам когда-либо понадобится.

Когда вы запрашиваете диапазон, вы можете лениво применять неприменимое количество обновлений и извлекать данные из правой корзины, если у рассматриваемого диапазона нет границы внутри диапазонаиндексы в этой части дерева.Тогда, и только тогда, вам нужно внести неприменимое количество обновлений во внутренние узлы.

Обе операции развертывают только часть дерева на границе и поэтому O(log(n)).