임의의 직사각형에 포함된 서로 다른 정수의 개수를 찾는 2차원 배열 누적합

14846번: 직사각형과 쿼리

 

n*n 배열에서 왼쪽 위가 (x1,y1), 오른쪽 아래가 (x2,y2)인 직사각형에 포함되는 서로 다른 정수의 개수를 찾는 쿼리가 많이 주어질 때 이 쿼리에 답한다

 

-------------------------------------------------------------------------------------------------------

 

n이 300인데 여기서 핵심은 행렬이 포함하고 있는 정수가 10까지라는 것이다

 

dp[y][x][i]를 왼쪽 위가 (0,0)이고 오른쪽 아래가 (x,y)인 직사각형에 포함된 정수 i의 개수로 정의한다

 

x,y가 300까지이고 i가 10까지니까 900000 정도로 메모리 적당

 

나머지는 여기서 배운 테크닉대로 하면 된다

 

https://deepdata.tistory.com/1031

2차원 배열에서의 누적합 배열을 구하는 방법 배우기

 

 

y = 0일때 x축으로 dp[0][x][i]를 채운다

 

dp[0][x][maps[0][x]] += 1을 하고, 모든 i = 1,2,3,..,10에 대하여 dp[0][x][i] += dp[0][x-1][i]

 

x = 0일때 y축으로 dp[y][0][i]를 채운다

 

dp[y][0][maps[y][0]] += 1을 하고, 모든 i = 1,2,3...,10에 대하여 dp[y][0][i] += dp[y-1][0][i]

 

이후 x,y = 1,2,..,n-1에 대하여

 

dp[y][x][maps[y][x]] += 1을 하고 모든 i = 1,2,3...,10에 대하여

 

dp[y][x][i] = dp[y-1][x][i] + dp[y][x-1][i] - dp[y-1][x-1][i]

 

from sys import stdin

n = int(stdin.readline())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

dp = [[[0]*11 for _ in range(n)] for _ in range(n)]

dp[0][0][maps[0][0]] = 1

for x in range(1,n):      
    
    dp[0][x][maps[0][x]] += 1
    
    for i in range(1,11):

        dp[0][x][i] += dp[0][x-1][i]
        
for y in range(1,n):
    
    dp[y][0][maps[y][0]] += 1
    
    for i in range(1,11):
        
        dp[y][0][i] += dp[y-1][0][i]
            
for y in range(1,n):

    for x in range(1,n):
        
        dp[y][x][maps[y][x]] += 1
        
        for i in range(1,11):
            
            dp[y][x][i] += (dp[y-1][x][i] + dp[y][x-1][i] - dp[y-1][x-1][i])

 

 

이후에 쿼리 (x1,y1), (x2,y2)가 주어지면... 서로 다른 정수의 개수를 찾는 방법은?

 

모든 i = 1,2,..,10에 대하여 사각형 내부에 i의 개수를 찾는다

 

dp[y2][x2][i] - dp[y1-1][x2][i] - dp[y2][x1-1][i] + dp[y1-1][x1-1][i]

 

이 값이 1 이상이면, 해당 사각형 내부에는 정수 i가 1개 이상 있다는 뜻이므로, 1을 더해준다

 

0이면 정수 i가 존재하지 않으니 0을 더해주는

 

q = int(stdin.readline())

for _ in range(q):
    
    y1,x1,y2,x2 = map(int,stdin.readline().split())

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    count = 0

    for i in range(1,11):
        
        A = dp[y2][x2][i]

        if y1 == 0:
            
            B = 0
        
        else:

            B = dp[y1-1][x2][i]

        if x1 == 0:
            
            C = 0
        
        else:

            C = dp[y2][x1-1][i]
        
        if x1 == 0 or y1 == 0:

            D = 0

        else:

            D = dp[y1-1][x1-1][i]
        
        count += min((A - B - C + D),1)
    
    print(count)