Условие

Вам необходимо ответить на запросы — узнать сумму всех элементов числовой матрицы N×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

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer

fun main(args: Array<String>) {
    // Используем BufferedReader для быстрого чтения ввода
    val reader = BufferedReader(InputStreamReader(System.`in`))
    // Используем BufferedWriter для быстрого вывода
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Читаем размеры матрицы N, M и количество запросов K
    var tokenizer = StringTokenizer(reader.readLine())
    val n = tokenizer.nextToken().toInt()
    val m = tokenizer.nextToken().toInt()
    val k = tokenizer.nextToken().toInt()

    // Создаем матрицу префиксных сумм размером (N+1) x (M+1)
    // Используем Long для избежания переполнения при больших суммах
    val prefixSum = Array(n + 1) { LongArray(m + 1) }

    // Заполняем матрицу префиксных сумм
    for (i in 1..n) {
        tokenizer = StringTokenizer(reader.readLine())
        for (j in 1..m) {
            // Читаем текущий элемент матрицы
            val currentElement = tokenizer.nextToken().toLong()
            // Вычисляем префиксную сумму для ячейки (i, j)
            // Формула: P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
            // где A - исходная матрица, P - матрица префиксных сумм
            // Индексация в prefixSum смещена на 1 для удобства расчетов
            prefixSum[i][j] = currentElement + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
        }
    }

    // Обрабатываем K запросов
    repeat(k) {
        tokenizer = StringTokenizer(reader.readLine())
        // Читаем координаты верхнего левого (x1, y1) и нижнего правого (x2, y2) углов прямоугольника
        val x1 = tokenizer.nextToken().toInt()
        val y1 = tokenizer.nextToken().toInt()
        val x2 = tokenizer.nextToken().toInt()
        val y2 = tokenizer.nextToken().toInt()

        // Вычисляем сумму в заданном прямоугольнике с помощью префиксных сумм
        // Формула: Sum(x1, y1, x2, y2) = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]
        val sum = prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1]

        // Выводим результат для текущего запроса
        writer.write(sum.toString())
        writer.newLine() // Переходим на новую строку для следующего вывода
    }

    // Очищаем буфер и закрываем writer, чтобы убедиться, что все данные записаны
    writer.flush()
    writer.close()
    // Закрываем reader
    reader.close()
}