Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_15_08 - Nowa waluta 2

Mieszkańcy p państw położonych wzdłuż linii wybrzeża naszego kontynentu mają już dość noszenia ogromnej liczby monet w swoich sakiewkach, które pod ich ciężarem często się przerywają. W związku z powyższym władcy niektórych krajów sąsiadujących ze sobą raz na jakiś czas podejmują próbę wprowadzenia nowej waluty, minimalizując jednocześnie liczbę monet będących w obiegu. Niestety próby te przeważnie kończą się niepowodzeniem. Czasami wynika to ze zmiany liczby monet w jednym z państw, co powoduje konieczność rozpoczęcia obliczeń od nowa. Innym razem władcy zdążą się pokłócić przed wprowadzeniem nowej waluty i formują inną grupę krajów. Jako, że masz już dość zaistniałej sytuacji, postanowiłeś napisać program, który przyspieszy obliczenia.

Program powinien umożliwiać wykonanie dowolnej liczby operacji. Możliwe operacje to:

  • Zmiana liczby monet w państwie na pozycji a na wartość b.
  • Obliczenie ile łącznie monet należy wybić, w przypadku gdy nową walutę chcą wprowadzić kraje znajdujące się na pozycjach od a do b włącznie. Należy pamiętać, że liczba monet powinna być jak najmniejsza, zaś stosunek liczby nowych monet dowolnej pary państw musi być identyczny jak w przypadku starej waluty. W związku z tym, że jest to jedynie symulacja liczba monet w danych państwach nie ulega zmianie.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite p oraz q (1 ≤ p, q ≤ 105) oznaczające odpowiednio liczbę państw oraz liczbę operacji do wykonania. W drugiej linii wejścia znajduje się p liczb z przedziału od 1 do 109 określających bieżącą liczbę monet w danym państwie. W kolejnych q liniach znajdują się zapytania. Każde z nich składa się z trzech liczb t, a oraz b. Liczba t (0 ≤ t ≤ 1) określa typ operacji do wykonania. Wartość t równa 0 określa, że należy zaktualizować liczbę monet w państwie a (1 ≤ ap) na liczbę b (1 ≤ b ≤ 109). Wartość t równa 1 określa konieczność obliczenia łącznej liczby monet do wybicia dla państw w przedziale od a do b (1 ≤ a < bp).

Wyjście

Dla każdego zapytania z t równym 1 należy w osobnej linii wypisać łączną liczbę monet nowej waluty jakie zostaną wybite dla państw w przedziale od a do b.

Przykład

Wejście

4 5
2 8 4 6
1 1 4
1 2 3
0 1 8
0 4 8
1 1 4

Wyjście

10
3
7

Dodane przez:Maciej Boniecki
Data dodania:2014-03-29
Limit czasu wykonania programu:0.300s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.