Реализуйте структуру данных для эффективного вычисления сумм подряд идущих элементов массива.
В первой строке вводится одно натуральное число \(N\) \((1 \leq N \leq 100000)\) — количество чисел в массиве.
Во второй строке вводятся \(N\) чисел от \(1\) до \(100000\) — элементы массива.
В третьей строке вводится одно натуральное число \(K\) \((1 \leq K \leq 30000)\) — количество запросов на вычисление суммы.
В следующих \(K\) строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).'
Для каждого запроса выведите сумму чисел соответствующего участка массива. Числа выводите в одну строку через пробел.
| Ввод | Вывод |
|---|---|
5 4 4 8 7 8 2 1 2 1 3 |
8 16 |
У Олега есть матрица целых чисел \(N \times M\). Его очень часто просят узнать сумму всех элементов матрицы в прямоугольнике с левым верхним углом (\(x_1\), \(y_1\)) и правым нижним (\(x_2\), \(y_2\)). Помогите ему в этом.
В первой строке находится числа \(N, M\) размеры матрицы (\(1 \leq N, M \leq 1000\)) и \(K\) - количество запросов (\(1 \leq K \leq 100000\)). Каждая из следующих \(N\) строк содержит по \(M\) чисел --- элементы соответствующей строки матрицы (по модулю не превосходят \(1000\)). Последующие \(K\) строк содержат по \(4\) целых числа, разделенных пробелом - \(x_1\) \(y_1\) \(x_2\) \(y_2\) --- запрос на сумму элементов матрице в прямоугольнике (\(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M\))
Для каждого запроса на отдельной строке выведите его результат - сумму всех чисел в элементов матрице в прямоугольнике \((x_1,y_1)\), \((x_2,y_2)\)
| Ввод | Вывод |
|---|---|
3 3 2 1 2 3 4 5 6 7 8 9 2 2 3 3 1 1 2 3 |
28 21 |
Реализуйте структуру данных для эффективного вычисления количества нулей в отрезке массива.
В первой строке вводится одно натуральное число \(N\) \((1 \leq N \leq 100000)\) — количество чисел в массиве.
Во второй строке вводятся \(N\) чисел от \(0\) до \(100000\) — элементы массива.
В третьей строке вводится одно натуральное число \(K\) \((1 \leq K \leq 30000)\) — количество запросов на вычисление количества нулей.
В следующих \(K\) строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).
Для каждого запроса выведите количество нулей на соответствующем участке массива. Числа выводите в одну строку через пробел.
| Ввод | Вывод |
|---|---|
5 0 0 0 0 2 2 2 3 2 5 |
2 3 |
В школу бальных танцев профессора Падеграса записались \(n\) учеников — мальчиков и девочек. Профессор построил их в один ряд, и хочет отобрать из них для первого занятия группу стоящих подряд учеников, в которой количество мальчиков и девочек одинаково. Сколько вариантов выбора есть у профессора?
В первой строке задано число \(n\) \((1 \leq n \leq 10^{6})\). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из \(n\) символов \(a\) и \(b\) (символ a соответствует девочке, а символ b — мальчику).
В единственной строке должно содержаться единственное число—количество вариантов выбора требуемой группы.
| Ввод | Вывод |
|---|---|
8 aabbaabb |
10 |
Дан массив целых чисел. Найти отрезок этого массива с максимальной суммой.
В первой строке дано натуральное число \(n\) \((1 \leq n \leq 10^{5})\) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают \(10^{4}\).
Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.
| Ввод | Вывод |
|---|---|
5 -1 2 3 -2 5 |
2 5 8 |
Первая строка входного файла содержит числа \(n, m\) и \(r\) (\(2 \leq n, m \leq 2000\), \(2 \leq r \leq 10^9\)) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит \(m\) целых чисел – первую строку таблицы: \(a_{11}, a_{12}, \ldots, a_{1m}\). Все \(a_{1i}\) неотрицательны и не превосходят \(10^9\).
В первой строке выходного файла необходимо вывести \(m\) чисел – последнюю строку таблицы: \(a_{n1}, a_{n2}, \ldots, a_{nm}\).
| Ввод | Вывод |
|---|---|
2 3 10 1 2 3 |
3 6 5 |
3 3 10 1 1 1 |
8 0 8 |
Сегодня на страницах газеты «Математический досуг» была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из \(m\) строк и \(n\) столбцов. В каждой ячейке таблицы записано некоторое целое число.
Для решения головоломки требуется найти такой невырожденный прямоугольник с вершинами в центрах ячеек таблицы, и сторонами, параллельными сторонам таблицы, чтобы сумма чисел, записанных в ячейках на границе получившегося прямоугольника, была максимальна.
Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.
Напишите программу, которая по заданной таблице найдет искомый прямоугольник.
В первой строке вводятся два целых числа \(m\) и \(n\) (\(2 \le m, n \le 300\)). Далее следует описание таблицы – \(m\) строк, каждая из которых содержит по \(n\) целых чисел \(a_{i,j}\) (\(-10^4 \le a_{i,j} \le 10^4\)).
В первой строке выведите целое число \(s\) – максимальную сумму чисел на границе искомого прямоугольника. Во второй строке выведите четыре натуральных числа: \(x_1\), \(y_1\), \(x_2\), \(y_2\) – координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь \(x\) – номер строки, а \(y\) – номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.
| Ввод | Вывод |
|---|---|
2 3 1 1 1 1 1 1 |
6 1 1 2 3 |
5 4 9 -2 -1 3 -10 -5 1 -4 1 -1 2 -2 3 0 0 -1 2 2 -1 2 |
8 3 1 5 3 |