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

Задачи из рубрикатора

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

Условие задачи  
ID 30659: Сумма на отрезке
Сумма на отрезке
Темы: Префиксные суммы(минимумы, ...)   

Дан неизменяемый массив длины 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
ID 33256: Кот Гусь и случайная матрица
Кот Гусь и случайная матрица
Темы: Куча    Префиксные суммы(минимумы, ...)   

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера n × m, содержащую числа от 0 до p − 1.
Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p − 1, независимо от остальных.
Ваша задача — найти прямоугольную подматрицу этой таблицы, в которой сумма делится на p.
Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.
Формально, вам необходимо найти такие 1 <= i1 <= i2 <= n, 1 <= j1 <= j2 <= m, что сумма ax,y по всем i1 <= x <= i2, j1 <= y <= j2 делится на p, и среди таких имеет максимальную сумму.

Формат входных данных
В первой строке входного файла расположено три целых числа n, m, p (1 <= n·m, p <= 1 000 000) — размерности матрицы и число, на которое должна делится сумма подматрицы.
В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно ai,j (0 <= ai,j <= p − 1).
Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.

Формат выходных данных
Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p.
Если таких нет, выведите 0.

Ввод Вывод
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
 65

ID 29655: Рубка деревьев
Рубка деревьев
Темы: Префиксные суммы(минимумы, ...)   

Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей они используют 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