1의 개수 세기 2

문제 설명

0과 1로만 이루어진 이차원 배열 bits와 구간 합 쿼리 queries가 주어질 때, 각 쿼리 [x1, y1, x2, y2]에 대해 좌측 상단 (x1, y1)부터 우측 하단 (x2, y2)까지의 직사각형 부분 행렬 내 1의 개수를 반환하는 solution 함수를 작성하시오.

제한 사항

• bits는 NxM 크기의 직사각형 행렬 모양입니다.
  • N(=bits의 행 개수)은 1 이상 1,000 이하의 자연수입니다.
  • M(=bits의 열 개수)은 1 이상 1,000 이하의 자연수입니다.
• bits의 각 원소는 0 또는 1입니다.
• queries의 길이는 1 이상 200,000 이하입니다.
• queries의 각 원소는 [x1, y1, x2, y2]로 이루어져 있습니다.
  • 1 ≤ x1 ≤ x2 ≤ N(=bits의 행 개수)
  • 1 ≤ y1 ≤ y2 ≤ M(=bits의 열 개수)

예시 테스트케이스 설명

1번 테스트케이스 설명

• bits는 2x2 행렬입니다.

  1 0
  1 1
  

• 첫 번째 쿼리 [1,1,2,2]: (1,1)~(2,2) 전체 영역.
  • 1의 개수: 1+0+1+1 = 3
• 두 번째 쿼리 [1,2,2,2]: (1,2)~(2,2)

  0
  1
  

  • 1의 개수: 1

2번 테스트케이스 설명

• bits는 2x3 행렬입니다.

  0 1 0
  1 1 0
  

• 첫 번째 쿼리 [1,2,2,2]: (1,2)~(2,2)

  1
  1
  

  • 1의 개수: 2
• 두 번째 쿼리 [2,1,2,3]: (2,1)~(2,3)

  1 1 0
  

  • 1의 개수: 2
• 세 번째 쿼리 [1,1,1,3]: (1,1)~(1,3)

  0 1 0
  

  • 1의 개수: 1

3번 테스트케이스 설명

• bits는 3x4 행렬입니다.

  1 1 0 0
  0 1 1 1
  1 0 0 1
  

• 첫 번째 쿼리 [1,1,2,3]: (1,1)~(2,3)

  1 1 0
  0 1 1
  

  • 1의 개수: 4
• 두 번째 쿼리 [2,2,3,4]: (2,2)~(3,4)

  1 1 1
  0 0 1
  

  • 1의 개수: 4
• 세 번째 쿼리 [1,1,3,4]: (1,1)~(3,4)

  1 1 0 0
  0 1 1 1
  1 0 0 1
  

  • 1의 개수: 7