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

 

 

---

https://usaco.guide/silver/more-prefix-sums?lang=cpp#2d-prefix-sums 

More on Prefix Sums

 

 

---

※. 사각형의 높이 h 넓이 w가 1000이하 이므로 이중배열 사용가능

 

※. n이 10만 q가 10만 이므로 합을 일일이 구하기 보단 dp를 이용해 계산해준다.

 

※. hs ws hb wb 를 받았을 때 (hb-1, wb-1)의 사각형 개수 - (hs, ws)의 사각형 개수를 만족하는 사각형 넓이의 합을 구한다.

(hb wb 안에 사각형이 들어갈려면 hb wb보다 작으면(미만) 된다.)

( == (hb-1, wb-1)의 사각형 넓이 - (hs,ws)의 사각형 넓이를 구한다.)

 

※. 사각형이 있다면 dp[i][j]에 i*j(사각형의 넓이)를 저장해준다.

 

※. 모든 i, j를 탐색하며 (1000 * 1000) i,j의 사각형 넓이의 합을 구해준다. (i,j보다 작은 사각형이 있었다면 더해줘야한다.)

전체 사각형의 합을 구하는 법은 (빨간색 빗금) + (주황색 빗금) + (파란색 빗금) - (노란색, 두 번 더했기 때문에)

를 해주면 된다. == pref[i][j] = pref[i-1][j] + pref[i][j-1] + dp[i][j] - pref[i-1][j-1] 과 같다.

이 과정으로 pref[1000][1000]까지 구해주고

 

hs ws hb wb를 받을 때 다시 위와 같은 과정으로

ans(파란색 빗금) = 전체 사각형의 합 - (빨간색 빗금) - (주황색 빗금) + (노란색)을 해주면 된다.

 ans = pref[hb-1][wb-1](전체 사각형) - pref[hs][wb-1](빨간색 빗금) - pref[hb-1][ws](주황색 빗금) + pref[hs][ws](노란색)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	static long ans;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			int n = Integer.parseInt(st.nextToken());
 			int q = Integer.parseInt(st.nextToken());
 			long[][] pref = new long[1001][1001];
 			long[][] dp = new long[1001][1001];
 			for(int i = 1; i <= n; i++) {
 				st = new StringTokenizer(br.readLine(), " ");
 				int h = Integer.parseInt(st.nextToken());
 				int w = Integer.parseInt(st.nextToken());
 				dp[h][w] += h * w;
 			}
 			
 			for(int i = 1; i < 1001; i++) {
 				for(int j = 1; j < 1001; j++) {
 					pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + dp[i][j];
 				}
 			}
 			
 			for(int i = 0; i < q; i++) {
 				st = new StringTokenizer(br.readLine(), " ");
 				int hs = Integer.parseInt(st.nextToken());
 				int ws = Integer.parseInt(st.nextToken());
 				int hb = Integer.parseInt(st.nextToken());
 				int wb = Integer.parseInt(st.nextToken());
 				ans = 0;
 				ans = pref[hb-1][wb-1] - pref[hb-1][ws] - pref[hs][wb-1] + pref[hs][ws];
 				sb.append(ans).append('\n');
 			}
 		}
 		System.out.println(sb);
 	}
}