AlgoLiga 2018

Jakiś czas temu wsparliśmy inicjatywy wprowadzenia nowej waluty. Przypomnijmy sobie, o co chodziło.

Wzdłuż wybrzeża naszego kontynentu położonych jest p państw. Ich mieszkańcy narzekali na zbyt dużą liczbę monet w swoich sakiewkach w związku z czym niektóre sąsiadujące ze sobą kraje podejmowały próby wprowadzenia nowej waluty w celu zmniejszenia ich liczby. Nasze wsparcie polegało na stworzeniu oprogramowania, które umożliwiało przeprowadzenie dowolnej liczby operacji. Stworzony przez nas program obsługiwał dwa rodzaje operacji:

• Zmianę liczby monet w państwie na pozycji a na wartość b.
• Obliczenie ile łącznie monet należało wybić, w przypadku gdy nową walutę chciały wprowadzić kraje znajdujące się na pozycjach od a do b włącznie. Liczba monet miała być jak najmniejsza, zaś stosunek liczby nowych monet dowolnej pary państw musiał być identyczny jak w przypadku starej waluty.

Niestety pomimo naszego wsparcia żadna z inicjatyw nigdy nie weszła w życie. Dlaczego? Tego właśnie chce się dowiedzieć grupa badaczy, która poprosiła Ciebie o pomoc. Chodzi o zmodyfikowanie stworzonego wcześniej oprogramowania, tak aby umożliwiało ono obsługę danych historycznych. Nasz program powinien teraz obsługiwać poniższe dwa rodzaje operacji:

• 0 a b - zmiana liczby monet w państwie na pozycji a na wartość b.
• 1 i a b - Obliczenie ile łącznie monet należało wybić, w przypadku gdy po i zmianach (czyli po i pierwszych operacjach 0 a b) nową walutę chciały wprowadzić kraje znajdujące się na pozycjach od a do b włącznie. Liczba monet powinna być jak najmniejsza, zaś stosunek liczby nowych monet dowolnej pary państw musi być identyczny jak w przypadku starej waluty. Badacze gwarantują, że zapytanie 1 i a b poprzedzi co najmniej i operacji 0 a b.

Niestety nasi naukowcy zupełnie nie radzą sobie z obsługą komputera dlatego, jak już napiszesz program, zapraszają Ciebie na spotkanie żebyś go za nich obsługiwał. Badacze będą podawać Ci niezbędne dane i zapytania, a Ty masz udzielać im na nie odpowiedzi.

Wejście/Wyjście

Na początku naukowcy podadzą Ci dwie liczby całkowite p ∈ [1;10⁵] i q ∈ [1;2×10⁵] oznaczające odpowiednio liczbę krajów położonych wzdłuż wybrzeża oraz liczbę operacji, które będą chcieli wykonać. Następnie otrzymasz listę p liczb całkowitych z zakresu [1;10⁹] oznaczających początkową liczbę monet w każdym z państw. Innymi słowy jest to liczba monet przed jakąkolwiek zmianą czyli dla i równego 0. W końcu podadzą Ci q operacji do wykonania, w jednym z dwóch formatów, które zostały opisane w treści zadania:

• 0 a b gdzie a ∈ [1;p], b ∈ [1;10⁹]
• 1 i a b gdzie 1 ≤ a ≤ b ≤ p

Dla każdej operacji 1 i a b powinieneś podać odpowiedź.

Uwaga to jest zadanie interaktywne, po każdym wypisaniu odpowiedzi należy wczyścić bufor standardowego wyjścia! W przeciwnym wypadku sędzia nie otrzyma Twojej odpowiedzi, zaś wykonanie programu zakończy się werdyktem przekroczenia limitu czasu. Przykładowo w języku C++ do wyczyszczenia bufora można użyć wywołań: fflush(stdout); albo cout.flush();

Przykład

Oto jak może przebiegać Twoje spotkanie z badaczami.

Badacze:	5 17
Badacze:	6 63 21 13 52
Badacze:	1 0 1 5
Ty:		155
Badacze:	1 0 1 3
Ty:		30
Badacze:	1 0 4 5
Ty:		5
Badacze:	1 0 5 5
Ty:		1
Badacze:	0 4 6
Badacze:	0 5 156
Badacze:	1 1 1 5
Ty:		148
Badacze:	1 2 1 5
Ty:		84
Badacze:	1 1 2 4
Ty:		30
Badacze:	1 0 2 4
Ty:		97
Badacze:	0 3 126
Badacze:	0 2 126
Badacze:	1 0 1 5
Ty:		155
Badacze:	1 1 1 5
Ty:		148
Badacze:	1 2 1 5
Ty:		84
Badacze:	1 3 1 5
Ty:		119
Badacze:	1 4 1 5
Ty:		70