Страница: << 4 5 6 7 8 9 10 Отображать по:

#113283

Sparse table для суммы

Темы: [Динамическое программирование на таблицах] [Дерево отрезков, RSQ, RMQ]

Дан трёхмерный массив. Найдите сумму на параллелепипеде со сторонами, паралельными осям координат.

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

В первой строке даны три числа: 1 ≤ N , M , K ≤ 100 . В следующих N × M строках даны по K чисел - | a _ijk | < 10 ⁹ . Далее в отдельной строке даётся одно число Q ≤ 10 ⁹ - количество запросов. В следующих Q строках даются запросы: каждый запрос имеет вид x _{1

y} _{1

z} _{1

x} _{2

y} _{2

z} ₂ - две противоположные границы параллелепипеда, сумму которого необходимо подсчитать. 1 ≤ x ₁ ≤ x ₂ ≤ N 1 ≤ y ₁ ≤ y ₂ ≤ M 1 ≤ z ₁ ≤ z ₂ ≤ K

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

Для каждого запроса выведите одно число в отдельной строке - ответ на этот самый запрос

Примеры

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

3 3 3
2 3 5
1 2 3
4 5 7
1 6 6
9 6 6
8 6 6
4 3 3
2 3 3
5 3 3
1
2 1 2 3 3 3

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

Страница: << 4 5 6 7 8 9 10 Отображать по:

Выбрано

Отменить

Добавить в контест