eolymp
bolt
Try our new interface for solving problems
Məsələlər

Чебурашка и крокодил Гена

Чебурашка и крокодил Гена

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Когда Чебурашке и крокодилу Гене нечего делать, они играют в разные интересные игры. Сегодня Гена придумал новую игру, которая, по его мнению, поможет Чебурашке выучить арифметику. Правила игры очень просты: Гена возьмет n дощечек, пронумерует их от 1 до n и напишет на них какие-то числа. После чего он будет говорить два числа l и r, а Чебурашка будет должен посчитать сумму всех чисел на дощечках с номерами от l до r.

Также, чтобы Чебурашка не выучил все возможные ответы, Гена иногда меняет некоторые числа на другие, а именно все числа на промежутке [l, r]. Он не хочет сильно думать, поэтому просто пишет на этих дощечках числа от 1 до r - l + 1 по порядку. Чебурашка пока не очень хорошо знает арифметику, поэтому просит Вас написать ему программу, которая поможет ему в этом.

Giriş verilənləri

В первой строке находится количество дощечек n~(1 \le n \le 10^6). В следующей строке находится n чисел — начальные значения, написанные на дощечках (все числа не превышают 10^9). Далее следует количество запросов m~(1 \le m \le 10^5). Затем идет m строк, первое число в строке — это вид запроса t~(1 \le t \le 2).

  • Если t = 1, то далее следуют два числа l и r. Вам надо посчитать сумму всех чисел на дощечках с номерами от l до r;

  • Если t = 2, то далее следуют два числа l и r. Это означает, что на дощечках с номерами от l до r будут теперь числа от 1 до r - l + 1 соответственно.

Гарантируется, что все промежутки корректны. Нумерация дощечек начинается с единицы.

Çıxış verilənləri

Для каждого запроса с номером 1 выведите сумму чисел на промежутке [l, r].

Nümunə

Giriş verilənləri #1
5
5 3 2 4 5
5
1 1 5
1 2 3
2 1 5
2 2 5
1 1 5
Çıxış verilənləri #1
19
5
11
Müəllif Александр Бурков
Mənbə Дистанционная Летняя Компьютерная Школа - лето 2013 года