큰 사각형과 작은 사각형을 뺀다는 개념으로 문제를 접근해야 한다.
사각형들의 넓이를 dp배열에 저장해나가면서 풀어나가는 게 포인트다.
#include <iostream>
using namespace std;
int n, m, k;
int arr[301][301];
int dp[301][301];
int karr[10001];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> arr[i][j];
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
}
}
cin >> k;
int i, j, x, y;
for (int t = 0; t < k; t++)
{
cin >> i >> j >> x >> y;
karr[t] = dp[x][y] - (dp[i - 1][y] + dp[x][j - 1] - dp[i - 1][j - 1]);
}
for (int t = 0; t < k; t++)
cout << karr[t] << endl;
return 0;
}