基础算法之差分
# 差分 以空间换时间 d\[i\] = a\[i\]-a\[i-1\] \-> d\[i\]+=a\[i\]; d\[i+1\]-=a\[i\]; # ⼀维差分 ## 1,题目  ## 2,链接 [https://ac.nowcoder.com/acm/problem/226303](https://ac.nowcoder.com/acm/problem/226303 "https://ac.nowcoder.com/acm/problem/226303") ## 3,解析 因为中间添加数字一样,所以用差分数组 每次循环只需要 d\[l\] += k; d\[r+1\] -= k; 最后还原数组 d\[i\] = d\[i-1\]+d\[i\]; ## 4,代码 ```cpp #include using namespace std; typedef long long ll; const int N = 1e5+8; ll a[N],d[N]; int main(){ int n,m; cin >> n >> m; for(int i = 1;i > a[i]; d[i] += a[i]; d[i+1] -=a[i]; } while(m--){ int l,r,k; cin >> l >> r >> k; d[l]+=k; d[r+1]-=k; } for(int i = 1;i差分 ## 4,代码 ```cpp #include typedef long long ll; using namespace std; const int N = 1e5+8; int d[N]; int main(){ int n,m; cin >> n >>m; int x; cin >> x; for(int i = 2;i > y; if(x >y){ d[y]++; d[x]--; } else{ d[x]++; d[y]--; } x = y; } for(int i = 1;i > a >> b >> c; ret += min(a*d[i],c+b*d[i]); } cout using namespace std; typedef long long ll; const int N = 1010; ll f[N][N]; void insert(int r1,int c1,int r2,int c2,ll k){ f[r1][c1] +=k; f[r1][c2+1] -= k; f[r2+1][c1] -= k; f[r2+1][c2+1] += k; } int main(){ int n,m,q; cin >> n >> m >> q; for(int i = 1;i > x; insert(i,j,i,j,x); } } while(q--){ ll x1,y1,x2,y2,k; cin >> x1 >> y1 >> x2 >> y2 >> k; insert(x1,y1,x2,y2,k); } for(int i = 1;i using namespace std; const int N = 1010; int f[N][N]; void insert(int r1,int c1,int r2,int c2){ f[r1][c1] += 1; f[r1][c2+1]-=1; f[r2+1][c1]-=1; f[r2+1][c2+1]+=1; } int main(){ int n,m; cin >> n >> m; while(m--){ int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; insert(x1,y1,x2,y2); } for(int i = 1;i <= n;i++){ for(int j =1;j <= n;j++){ f[i][j] = f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1]; cout << f[i][j] << " "; } cout << endl; } return 0; } ```