POJ 2215 - Parliament

http://poj.org/problem?id=2215

概要

\(R \times S\) のマスがあり、各マスには整数が書かれている。 \(D\) 個の「\((R_1, S_1)\) を左上の端点とし、\((R_2, S_2)\) を右下の端点とする長方形の領域のマスの数値の合計値を求めよ」というクエリに答える。

制約

• \(1 \le R_1 \le R_2 \le R \le 1000\)
• \(1 \le S_1 \le S_2 \le S \le 1000\)
• すべてのマスの数値の合計は int の範囲に収まる

解法

二次元累積和を計算するだけ。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int T;
 8   scanf("%d", &T);
 9   while (T-- > 0) {
10     int R, C;
11     scanf("%d %d", &R, &C);
12     static long long sums[1001][1001];
13     for (int i = 0; i <= R; i++) {
14       fill_n(sums[i], C+1, 0);
15     }
16     for (int i = 0; i < R; i++) {
17       for (int j = 0; j < C; j++) {
18         int x;
19         scanf("%d", &x);
20         sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + x;
21       }
22     }
23 
24     int D;
25     scanf("%d", &D);
26     while (D-- > 0) {
27       int r1, c1, r2, c2;
28       scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
29       printf("Absolutni hodnota pohodlnosti je %lld bodu.\n", sums[r2][c2] - sums[r1-1][c2] - sums[r2][c1-1] + sums[r1-1][c1-1]);
30     }
31     putchar('\n');
32   }
33   return 0;
34 }