# 11594: 【原1594】求和

### 题目描述

author: Spy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1594

# Description

## Sample Input

3 7 2
5 3 4 8 8 6 3
0 4 1 6 1 3 3
6 2 9 0 4 3 9
1 6 1 7
2 2 3 7


## Sample Output

9
45


## BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

int main() {
int N, M, Q;
cin >> N >> M >> Q;
auto table = new ll *[N + 1];
for (int i = 0; i <= N; ++i) {
table[i] = new ll[M + 1]{};
}

int tmp;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
scanf("%d", &tmp);
table[i][j] = table[i][j - 1] + table[i - 1][j] - table[i - 1][j - 1] + tmp;
}
}

int x1, y1, x2, y2;
while (Q--) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
ll ans = table[x2][y2] - table[x1 - 1][y2] - table[x2][y1 - 1] + table[x1 - 1][y1 - 1];
if (ans < 0) ans = -ans;
printf("%lld\n", ans);
}

for (int i = 0; i <= N; ++i) {
delete[] table[i];
}
delete[] table;
return 0;
}


## FineArtz's solution

/* 求和 */
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAXS = 5e3 + 5;
long long sum[MAXS][MAXS] = {0};

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m, n, q, t;
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
cin >> t;
sum[i][j] = t + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
int x1, x2, y1, y2;
long long ans = 0;
while (q--){
cin >> x1 >> y1 >> x2 >> y2;
ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
cout << ans << '\n';
}
return 0;
}


## ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

constexpr int max_num = 120000009;

long long a[max_num] = { 0 };
int N, M, Q;
long long f(int posx, int posy) {
return a[posx * (M + 1) + posy];
}

int main() {

scanf("%d %d %d", &N, &M, &Q);

for (int i = 1; i <= N; ++i) {
a[i * (M + 1)] = a[(i - 1) * (M + 1) + 1];
for (int j = 1; j <= M; ++j) {
long long temp;
scanf("%lld", &temp);
a[i * (M + 1) + j] = temp + a[(i - 1) * (M + 1) + j]
+ a[i * (M + 1) + j - 1] - a[(i - 1) * (M + 1) + j - 1];
}
}

for (; Q > 0; --Q) {
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
printf("%lld\n", f(x2, y2) - f(x2, y1 - 1) - f(x1 - 1, y2) + f(x1 - 1, y1 - 1));
}

return 0;
}


## q4x3's solution

#include <stdio.h>
#include <cstring>

using namespace std;

int q[10000010][4];

int main()
{
int N, M, Q;
scanf("%d%d%d", &N, &M, &Q);
int **a;
long long **map;
a = new int*[N + 1];
map = new long long int*[N + 1];
for(int i = 0;i <= N;++ i) {
a[i] = new int[M + 1];
map[i] = new long long[M + 1];
}
for(int i = 0;i <= N;++ i)
for (int j = 0;j <= M;++ j) {
a[i][j] = 0;
map[i][j] = 0;
}
for(int i = 1;i <= N;++ i)
for (int j = 1;j <= M;++ j)
scanf("%d", &a[i][j]);
for(int i = 1;i <= Q;++ i)
scanf("%d%d%d%d",&q[i][0],&q[i][1],&q[i][2],&q[i][3]);
for(int i = 1;i <= N;++ i)
for(int j = 1;j <= M;++ j)
map[i][j] = map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1] + a[i][j];
for(int i = 1;i <= Q;++ i) {
printf("%lld\n", map[q[i][2]][q[i][3]] + map[q[i][0] - 1][q[i][1] - 1] - map[q[i][2]][q[i][1] - 1] - map[q[i][0] - 1][q[i][3]]);
}

}


## skyzh's solution

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int M, N, Q;
int MAP[10000002] = { 0 };
long long SUM[10000002] = { 0 };

int main() {
scanf("%d%d%d", &N, &M, &Q);
for (int i = 0, k = 0; i < N; i++) {
for (int j = 0; j < M; j++, k++) {
scanf("%d", &MAP[k]);
}
}

SUM[0] = MAP[0];

for (int j = 1; j < M; j++) {
SUM[j] = SUM[j - 1] + MAP[j];
}

int R = 0;
for (int i = 1; i < N; i++) {
R += M;
SUM[R] = SUM[R - M] + MAP[R];
for (int j = 1; j < M; j++) {
int C = R + j;
SUM[C] = SUM[C - 1] + SUM[C - M] - SUM[C - M - 1] + MAP[C];
}
}
register int x1, y1, x2, y2;
register long long res = 0;
register int P_TL, P_BR, P_TR, P_BL;
for (int i = 0; i < Q; i++) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
--x1; --y1; --x2; --y2;
res = 0;
P_TL = (x1 - 1) * M + (y1 - 1);
P_BR = x2 * M + y2;
P_TR = (x1 - 1) * M + y2;
P_BL = x2 * M + y1 - 1;
if (x1 == 0 && y1 == 0)
res = SUM[P_BR];
else if (x1 == 0)
res = SUM[P_BR] - SUM[P_BL];
else if (y1 == 0)
res = SUM[P_BR] - SUM[P_TR];
else {
res = SUM[P_BR] + SUM[P_TL] - SUM[P_TR] - SUM[P_BL];
}
printf("%lld\n", res);
}
return 0;
}


## WashSwang's solution

#include <iostream>
using namespace std;
int a[10000001],n,m,q,x1,x2,y1,y2;
long long map[10000001],ans;
int main() {
scanf("%d%d%d",&n,&m,&q);
for (int i=0;i<n*m;++i){
scanf("%d",&a[i]);
if (i>=m) map[i]+=map[i-m];
if (i%m!=0) map[i]+=map[i-1];
if (i>=m&&i%m!=0) map[i]-=map[i-m-1];
map[i]+=a[i];
}
for (int i=0;i<q;++i){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1-=1;
y1-=1;
x2-=1;
y2-=1;
ans=map[x2*m+y2];
if (y1>0) ans-=map[x2*m+y1-1];
if (x1>0) ans-=map[(x1-1)*m+y2];
if (x1>0&&y1>0) ans+=map[(x1-1)*m+y1-1];
printf("%lld\n",ans);
}
return 0;
}