11594: 【原1594】求和

题目

题目描述

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

Description

子虚年乌有月，亡是国兵败，亡是公欲割地以求和。

已知：

亡是国疆域内有\(N*M\)座呈矩形分布的封城。

每座封城的人口数由一个二维数组给出\({a[1][1],a[1][2],…,a[N][M]}\).

亡是公有\(Q\)个割地方案，他会给出割地的边界 \(x1,y1,x2,y2\)，每个方案中包含的领地是连续的。

对于每个方案包含的人口数量\(a[x1][y1]+a[x1][y1+1]+…+a[x2][y2]\)，亡是公希望你帮他求和。

Input Format

第一行有三个整数\(N,M,Q\) ，代表矩形边长和方案数。

接下来 \(N\) 行，每行\(M\) 个数，代表每个城市的人口。

接下来 \(Q\) 行，每行四个整数 \(x1,y1,x2,y2\)，代表求和区间。

Output Format

对于每个方案，输出区间内人口数的总和，每个询问输出一行。

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

Limits

对于\(100\%\)的数据，\(\forall i,j, a[i][j]\in [0,2147483647),1\leq x1\leq x2\leq N, 1\leq y1\leq y2\leq M\)。

对于\(60\%\)的数据，\(M*N,Q \leq 10^4\)

对于\(80\%\)的数据，\(M*N \leq 10^7, Q \leq 10^4\)

对于\(100\%\)的数据，\(M*N,Q \leq 10^7\)

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;
}