[Codeforces] 1722E. Counting Rectangles [Round #817 (Div.4)]

📚 문제 E: Counting Rectangles

📖 풀이

카운팅 배열 및 2차원 누적합 문제이다.

1001 1001로 배열 visited를 만들어 사각형의 h w를 visited[h][w]에 담아준다.

n이 10만까지이고 q도 10만까지이니 h, w는 1000까지니까 카운팅 배열을 활용해야 한다. 그냥 하나씩 확인하려고 하면 O(n^2)으로 무조건 시간초과가 발생한다.

카운팅 배열로 담아주고 q만큼 확인해주려고 해도 시간초과가 발생한다.

따라서 시간을 현저히 줄이기 위해 2차원 누적합을 활용한다.

백준 - 14846. 직사각형과 쿼리를 참고한다.

위 방법과 같이 누적합을 활용하면 쿼리 하나씩 확인하는 연산을 2중 for 문 최대 1000 * 1000 = 10만에서 4로 줄일 수 있다.

📒 풀이

t = int(input())
for _ in range(t):
    n, q = map(int, input().split())
    visited = [[0 for _ in range(1001)] for _ in range(1001)]
    for i in range(n):
        hi, wi = map(int, input().split())
        visited[hi][wi] += hi*wi
    # 2차원 누적합
    for i in range(1, 1001):
        for j in range(1, 1001):
            visited[i][j] = visited[i][j] + visited[i-1][j] + \
                visited[i][j-1] - visited[i-1][j-1]

    for i in range(q):
        hs, ws, hb, wb = map(int, input().split())
        ans = visited[hb - 1][wb - 1] - visited[hb - 1][ws] - \
            visited[hs][wb - 1] + visited[hs][ws]
        print(ans)

🔍 결과