题目描述

blablabla

样例

#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N][N],p[N][N];
// 主函数
signed main()
{
    // 输入数组的行数和列数
    int n,m;cin >> n >> m;
    // 输入查询次数
    int q;cin >> q;
    // 输入原始数组
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin >> a[i][j];
            // 计算差分数组
            p[i][j] = a[i][j] -a[i-1][j] - a[i][j-1] + a[i-1][j-1];
        }
    }
    // 处理每个查询
    while(q--){
        // 输入查询的左上角和右下角坐标
        int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;
        // 输入要修改的值
        int c;cin >> c;
        // 在差分数组上进行修改
        p[x1][y1] += c;
        p[x2+1][y1] -= c;
        p[x1][y2+1] -= c;
        p[x2+1][y2+1] += c;
    }
    // 还原原始数组
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            a[i][j] = p[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    // 程序结束
    return 0;
}

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla