누적 합2차원 목록큰 정수(64비트)P0092

격자에서 직사각형 합 빨리 구하기

r줄 c칸짜리 격자의 칸마다 정수가 하나씩 적혀 있다.
맨 위 줄이 1번 줄, 맨 왼쪽 칸이 1번 칸이다.
질문 q개가 주어지고, 각 질문은 네 수 r₁ c₁ r₂ c₂로 '줄 r₁~r₂, 칸 c₁~c₂(양 끝 포함)로 이루어진 직사각형 안의 수를 모두 더한 값'을 묻는다.
질문마다 답을 한 줄씩, 주어진 차례대로 출력하라. 첫 줄에 r, c, q, 그다음 r줄에 각 줄의 수 c개, 그다음 q줄에 질문이 빈칸으로 나뉘어 주어진다.

입력: 1 ≤ r, c ≤ 100, 1 ≤ q ≤ 10,000, 칸의 수는 -10⁶ 이상 10⁶ 이하, 1 ≤ r₁ ≤ r₂ ≤ r, 1 ≤ c₁ ≤ c₂ ≤ c
출력: q줄, 질문마다 직사각형의 합

예시 1 · stdin

stdout

78
34
24

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

질문마다 칸을 다시 더하면 최대 1만 질문 × 1만 칸 = 1억 번이에요.
Python은 시간 안에 못 끝내고, 크레이콘은 실행 걸음 한도(약 5천만)를 넘어 멈춰요.
2차원 누적 합 P[i][j] = '(1,1)부터 (i,j)까지 직사각형의 합'을 P[i][j] = a[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]로 한 번 만들면(0번 줄·칸은 0), 답은 P[r₂][c₂] - P[r₁-1][c₂] - P[r₂][c₁-1] + P[r₁-1][c₁-1]로 바로 나와요.
함정 셋: r₁-1, c₁-1 대신 r₁, c₁로 빼면 맨 윗줄과 맨 왼쪽 칸이 빠져요.
두 번 뺀 왼쪽 위 조각을 다시 더하는 것을 잊기 쉬워요.
그리고 합이 최대 10⁴ × 10⁶ = 10¹⁰이라 C·C++·Java·C#에서 int(약 21억)에 담으면 넘쳐요 — long/long long을 써요.
Python은 정수 크기에 끝이 없고, JavaScript·TypeScript·크레이콘은 2^53까지 정확해서 괜찮아요.
2차원 배열 만들기가 언어마다 달라요: Python [[0] * (c + 1) for _ in range(r + 1)]([[0] * (c + 1)] * (r + 1)는 같은 줄을 여러 번 가리켜서 틀려요), JS Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0)), Java new long[r + 1][c + 1](0으로 채워짐), C# 직사각형 배열 new long[r + 1, c + 1]과 P[i, j], C 전역 long long P[101][101], C++ vector<vector<long long>>.
크레이콘은 줄마다 새목록(c + 1, 0)을 P.넣기(…)로 쌓아요 — 줄 하나가 101칸이라 목록 한도(10,000개) 걱정이 없어요.

Pythonmain.py · 19 줄

import sys data = sys.stdin.buffer.read().split()r, c, q = int(data[0]), int(data[1]), int(data[2])pos = 3 # P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다P = [[0] * (c + 1) for _ in range(r + 1)]for i in range(1, r + 1):    for j in range(1, c + 1):        P[i][j] = int(data[pos]) + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]        pos += 1 out = []for _ in range(q):    r1, c1, r2, c2 = map(int, data[pos:pos + 4])    pos += 4    out.append(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1])print("\n".join(map(str, out)))

JavaScriptmain.js · 19 줄

const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [r, c, q] = t;let pos = 3; // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다const P = Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0));for (let i = 1; i <= r; i++) {  for (let j = 1; j <= c; j++) {    P[i][j] = t[pos++] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];  }} const out = [];for (let k = 0; k < q; k++) {  const [r1, c1, r2, c2] = t.slice(pos, pos + 4);  pos += 4;  out.push(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);}console.log(out.join("\n"));

TypeScriptmain.ts · 20 줄

import { readFileSync } from "node:fs";const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [r, c, q] = t;let pos = 3; // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다const P: number[][] = Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0));for (let i = 1; i <= r; i++) {  for (let j = 1; j <= c; j++) {    P[i][j] = t[pos++] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];  }} const out: number[] = [];for (let k = 0; k < q; k++) {  const [r1, c1, r2, c2] = t.slice(pos, pos + 4);  pos += 4;  out.push(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);}console.log(out.join("\n"));

JavaMain.java · 30 줄

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(br.readLine());        int r = Integer.parseInt(st.nextToken()), c = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());         // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0(자바 배열은 0으로 채워진다)        long[][] P = new long[r + 1][c + 1];        for (int i = 1; i <= r; i++) {            st = new StringTokenizer(br.readLine());            for (int j = 1; j <= c; j++) {                P[i][j] = Long.parseLong(st.nextToken()) + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];            }        }         StringBuilder out = new StringBuilder();        for (int k = 0; k < q; k++) {            st = new StringTokenizer(br.readLine());            int r1 = Integer.parseInt(st.nextToken()), c1 = Integer.parseInt(st.nextToken());            int r2 = Integer.parseInt(st.nextToken()), c2 = Integer.parseInt(st.nextToken());            out.append(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]).append('\n');        }        System.out.print(out);    }}

C#Main.cs · 26 줄

using System;using System.Text; class Program{    static void Main()    {        string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);        int r = int.Parse(t[0]), c = int.Parse(t[1]), q = int.Parse(t[2]);        int pos = 3;         // P[i, j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0        long[,] P = new long[r + 1, c + 1];        for (int i = 1; i <= r; i++)            for (int j = 1; j <= c; j++)                P[i, j] = long.Parse(t[pos++]) + P[i - 1, j] + P[i, j - 1] - P[i - 1, j - 1];         var sb = new StringBuilder();        for (int k = 0; k < q; k++, pos += 4)        {            int r1 = int.Parse(t[pos]), c1 = int.Parse(t[pos + 1]), r2 = int.Parse(t[pos + 2]), c2 = int.Parse(t[pos + 3]);            sb.Append(P[r2, c2] - P[r1 - 1, c2] - P[r2, c1 - 1] + P[r1 - 1, c1 - 1]).Append('\n');        }        Console.Write(sb);    }}

C++main.cpp · 24 줄

#include <iostream>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int r, c, q;    std::cin >> r >> c >> q;     // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다    std::vector<std::vector<long long>> P(r + 1, std::vector<long long>(c + 1, 0));    for (int i = 1; i <= r; i++) {        for (int j = 1; j <= c; j++) {            long long v;            std::cin >> v;            P[i][j] = v + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];        }    }    for (int k = 0; k < q; k++) {        int r1, c1, r2, c2;        std::cin >> r1 >> c1 >> r2 >> c2;        std::cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1] << '\n';    }}

Cmain.c · 24 줄

#include <stdio.h> #define MAX 100 /* P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0(전역 배열은 0으로 시작) */static long long P[MAX + 1][MAX + 1]; int main(void) {    int r, c, q;    scanf("%d %d %d", &r, &c, &q);    for (int i = 1; i <= r; i++) {        for (int j = 1; j <= c; j++) {            long long v;            scanf("%lld", &v);            P[i][j] = v + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];        }    }    for (int k = 0; k < q; k++) {        int r1, c1, r2, c2;        scanf("%d %d %d %d", &r1, &c1, &r2, &c2);        printf("%lld\n", P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);    }    return 0;}

Craykonmain.cray · 29 줄

첫줄 = 콘솔.수들읽기();r = 첫줄[0];c = 첫줄[1];q = 첫줄[2]; // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다P = [];반복 (i = 0; i <= r; i++){    P.넣기(새목록(c + 1, 0));}반복 (i = 1; i <= r; i++){    row = 콘솔.수들읽기();    반복 (j = 1; j <= c; j++)    {        P[i][j] = row[j - 1] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];    }} 반복 (k = 0; k < q; k++){    qq = 콘솔.수들읽기();    r1 = qq[0];    c1 = qq[1];    r2 = qq[2];    c2 = qq[3];    콘솔.쓰기(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);}