/>

Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Рубка деревьев

Префиксные суммы(минимумы, ...)

Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей они используют n деревьев, стоящих в ряд и пронумерованных от 1 до n. Чубатый оценил прочность всех деревьев натуральными числами и записал их. За каждое дерево, которое Мелехов смог разрубить, он получает количество очков равное числу, записанному на дереве, а если не смог - то теряет столько же.
Чубатый просит Григория выполнить удары на деревьях с l по r, в порядке возрастания их номеров. Мелехов недавно ушиб плечо, потому он может успешно срубить дерево через раз, т. е. если он срубил дерево с номером i, то он не сможет срубить дерево с номером i + 1, но сможет срубить дерево с номером i + 2 и т. д.
Мелехов m раз попросил Григория выполнить удары, но он забыл, какие деревья Мелехов смог срубить. Помогите ему определить, сколько очков набрал Григорий за каждую попытку.
 
Входные данные
В первое строке содержатся 2 числа n и m (1 <= n, m <= 100000)
Во второй строке содержатся n чисел - прочность всех деревьев, где на позиции i написана прочность дерева i.
В следующих m строках содержатся пары чисел l и r (1 <= l <= r <= n), означающие какой отрезок деревьев попросил срубить Чубатый.
 
Выходные данные
На каждый запрос выведите сколько очков в эту попытку заработал Григорий.

Ввод Вывод
6 6
1 2 3 4 5 6
1 6
1 5
2 6
2 5
2 4
2 2
57
-92
57
-130

(с) Григорьев Е., 2018

Сумма на отрезке

Префиксные суммы(минимумы, ...)

Дан неизменяемый массив длины n и q запросов типа “вычислить сумму подотрезка массива с l по r”. Выведите ответ на каждый запрос.

Входные данные:

В первой строке дано число n – размер массива (1 <= n <= 10^5).
Во второй строке дано n чисел – элементы массива. Числа по модулю не превосходят 10^9.
В третьей строке дано число q – кол-во запросов ( 1 <= q <= 10^5).
Далее дано q строк, в каждой из которых дано 2 числа: l и r (1 <= l <= r <= n).

Выходные данные:
Выведите ответы на все запросы, каждый в отдельной строке.

Ввод Вывод
5
1 2 3 4 5
3
1 2
3 3
2 5
3
3
14

(с) Курбатов Е., 2018