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

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

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

Условие задачи  
ID 33256: Кот Гусь и случайная матрица
Кот Гусь и случайная матрица
Темы: Префиксные суммы(минимумы, ...)    Куча   

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера \(n \cdot m\), содержащую числа от 0 до p−1. Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p−1, независимо от остальных.

Ваша задача — найти прямоугольную подматрицу этой таблицы, в которой сумма делится на p. Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.

Формально, вам необходимо найти такие \(1 <= i_1 <= i_2 <= n\), \(1 <= j_1 <= j_2 <= m\), что сумма ax,y по всем \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) делится на p, и среди таких имеет максимальную сумму.

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

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

 

Примеры
Входные данные Выходные данные
1
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 30699: Банды Фомина №2
Банды Фомина №2
Темы: Префиксные суммы(минимумы, ...)   

Банда Фомина состоит из n групп, в каждой из которых ai человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел ai (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – li и ri (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

 

Примеры
Входные данные Выходные данные
1 6
1 3 7 1 4 100
3
1 3
3 4
2 6
21
7
8400

ID 29640: Тихий дон №2
Тихий дон №2
Темы: "Два указателя"    Префиксные суммы(минимумы, ...)   

Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с любовником. 

Найдите максимальное суммарное счастье за L дней, в которые Аксинья будет проводить с мужем не более C дней.
 
Входные данные
В первой строке подается 3 числа: N – кол-во дней, L и C (\(1 <= L, C <= N <= 1 000 000\)).
Во второй строке содержится N чисел a_i (\(1 <= |a_i| <= 1 000 000 000\)).

Входные данные
Требуется вывести ответ на задачу.
 

 

Примеры
Входные данные Выходные данные
1 5 3 3
1 -1 2 -2 3
3

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\)), означающие какой отрезок деревьев попросил срубить Чубатый.
 
Выходные данные
На каждый запрос выведите сколько очков в эту попытку заработал Григорий.
 

 

Примеры
Входные данные Выходные данные
1
6 6
1 2 3 4 5 6
1 6
1 5
2 6
2 5
2 4
2 2
57
-92
57
-130

ID 30691: Банды Фомина
Банды Фомина
Темы: Префиксные суммы(минимумы, ...)   

Банда Фомина состоит из n групп, в каждой из которых ai человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\)

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел ai (\(1 <= a_i <= 2\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – li и ri (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

 

Примеры
Входные данные Выходные данные
1
6
1 2 1 1 2 2
3
1 3
3 4
2 6
2
1
8

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\)).

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

 

Примеры
Входные данные Выходные данные
1
5
1 2 3 4 5
3
1 2
3 3
2 5
3
3
14

ID 29638: Тихий Дон №3
Тихий Дон №3
Темы: Префиксные суммы(минимумы, ...)   

Наталья Коршунова очень скучает по Григорию Мелехову и хочет вернуться к нему. Но, к сожалению, Григорий любит Аксинью, поэтому Наталья решила доказать любимому, что она лучше нее.
Для этого Наталья отправилась к Григорию и заявила, что она может решить любую задачу, какую бы он ни предложил. Мелехов принял вызов.
 
Григорий дает Наталье массив A, состоящий из n целых неотрицательных чисел. Затем он просит ее сделать q однотипных операций, заключающихся в следующем: "Даны числа l, r и k. Далее для каждого индекса i от l до r происходит подстановка числа k вместо числа Ai и считается побитовое исключающее “или” всех чисел на отрезке \([l;r]\), после чего на iое место опять возвращается число Ai".
Таким образом, происходит \(r – l + 1\) независимых подстановок, не меняющих массив, и соответственно \(r – l + 1\) результатов побитового исключающего “или”. Наталье необходимо сообщить Григорию побитовое исключающее “или” всех результатов подстановок (для лучшего понимания ознакомьтесь с примерами).
 
Помогите Наталье Коршуновой справиться с этой задачей! Тогда Григорий точно вернется к ней!
 
Входные данные
В первой строке дано целое число n (\(1 <= n <= 10^5\)) – количество элементов массива.
Во второй строке содержится n целых неотрицательных чисел, не превышающих по значению \(10^8\).
В третьей строке дано целое число q (\(1 <= q <= 10^5\)) – количество запросов.
Далее содержится q строк, в каждой из которых содержится 3 целых числа: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
 
Выходные данные
Вам необходимо вывести q ответов на каждый запрос в одной строке через пробел.
 

 

Примеры
Входные данные Выходные данные
1
5
1 2 3 4 5
2
1 3 7
4 5 10
7 1


Пояснение
Первый запрос:
1) 7 ⊕ 2 ⊕ 3 = 6
2) 1 ⊕ 7 ⊕ 3 = 5
3) 1 ⊕ 2 ⊕ 7 = 4
6 ⊕ 5 ⊕ 4 = 7
Ответ: 7.
 
Второй запрос:
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Ответ: 1.