AcWing 差分一维加二维

一维

#include<bits/stdc++.h>
using namespace std ;
const int N=100010;
int n,m;
int a[N],b[N];  //a为前缀和,b为差分        差分和前缀和互为逆运算
void insert(int l,int r,int c) {
    b[l]+=c;
    b[r+1]-=c;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) insert(i,i,a[i]);
    while(m--) {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1; i<=n; i++) b[i]+=b[i-1];  //把b数组变为自己的前缀和 
    for(int i=1; i<=n; i++) cout<<b[i]<<" ";
    return 0;
}
//假定a初始时全部为0,b初始也全部为0
//m个操作,让前缀和 l 到 r区间每个数字都加上c时,那么就让b数组的l加上c,r+1减去c
 

 

二维

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);  // 
    while (q -- ) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }
    return 0;
}
}

 

AcWing 差分一维加二维

上一篇:20款高质量的 HTML5 网站模板【免费下载】


下一篇:jQuery(function(){})与(function(){})(jQuery)的区别