题解 | 【模板】二维差分

【模板】二维差分

https://www.nowcoder.com/practice/50e1a93989df42efb0b1dec386fb4ccc

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  做这一题之前最好先做差分(一维),然后根据一维中的原数组是差分数组的前缀和就可以大概感觉出二位差分与原数组的关系,然后画图来推需要的操作,再去网上看看和别人的一不一样,是否要优化。
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n, m, q;
  cin >> n >> m >> q;
  vector<vector<long long>> a(n + 1, vector<long long>(m + 1, 0)), b(n + 1, vector<long long>(m + 1, 0));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      cin >> a[i + 1][j + 1];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
  int x, y, xx, yy, k;
  while(q--){
    cin >> x >> y >> xx >> yy >> k;
    b[x][y] += k;
    if (yy + 1 <= m)
      b[x][yy + 1] -= k;
    if (xx + 1 <= n)
      b[xx + 1][y] -= k;
    if (yy + 1 <= m && xx + 1 <= n)
      b[xx + 1][yy + 1] += k;
  }
  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m; j++){
      a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
      cout << a[i][j] << " ";
    }
    cout << "\n";
  }
}
// 64 位输出请用 printf("%lld")

#写题解领奖励##牛客春招刷题训练营#
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:35
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-25 13:59
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务