求助,差分矩阵
  • 板块学术版
  • 楼主Reverist
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/26 20:09
  • 上次更新2023/10/27 09:52:21
查看原帖
求助,差分矩阵
807209
Reverist楼主2022/9/26 20:09
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, q;
int sum[2111][2111];
int add[2111][2111];
int a, b, c, d, e;

signed main () {
  scanf ("%lld%lld%lld", &n, &m, &q);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf ("%lld", &sum[i][j]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      printf ("%lld ", sum[i][j]);
    }
    printf ("\n");
  }
  for (int i = 1; i <= q; i++) {
    scanf ("%lld%lld%lld%lld%lld",
            &a, &b, &c, &d, &e);
    d++;
    for (int j = a; j <= c; j++) {
      add[j][b] += e;
      add[j][d] -= e;
    }
  }
  int R = 0;
  for (int i = 1; i <= n; i++) {
    R = 0;
    for (int j = 1; j <= m; j++) {
      R += add[i][j];
      printf ("%lld ", sum[i][j] + R);
    }
    R += add[i][m + 1];
    printf ("\n");
  }
}
/*

10 10 10
1  1  4  5  1  4  1  9  1  9
2  2  5  1  3  3  4  6  1  5
-5 -8 -2 -3 -6 -2 -1 8  2  -5
7  2  6  -7 8  1  0  2  -4 5
64 48 34 99 61 97 60 11 45 14
-15 6 -14 0 -99 2 -22 3 -95 3
11 66 22 74 23 59 78 63 25 41
22 26 57 12 38 32 42 68 14 59
-5 -8 -2 -3 -6 -2 -1 89 28 -5
77 22 66 -7 88 12 20 42 -4 25

1 1 2 2 1
1 1 2 2 -2
1 1 10 10 1000
1 1 10 10 -1000
2 3 7 8 10
2 3 4 5 -10
5 6 7 8 -10
5 3 7 5 -10
2 6 4 8 -10
1 1 2 2 1
*/

上面这组数据是我手搓的,官方数据也过了,是

Input:
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

Output:
2 3 4 1
4 3 4 1
2 2 2 2

但是测试的时候 0pts,不知道为什么,在线求助,万分感谢

2022/9/26 20:09
加载中...