第一章：6.差分+前缀和（一个区域整体添加一个数）

1.【模板】差分

 

//#include<iostream> // //using namespace std; // //#include<iostream> // //using namespace std; // //typedef long long LL; // //const int N = 1e5 + 10; //int n, m; //LL a[N],f[N]; // //int main() //{ // cin >> n >> m; // for (int i = 1; i <= n; i++) // { // cin >> a[i]; // f[i] = a[i] - a[i - 1]; // } // // while (m--) // { // int l, r, k; cin >> l >> r >> k; // f[l] += k, f[r + 1] -= k; // } // // for (int i = 1; i <= n; i++) // { // a[i] = a[i - 1] + f[i]; // cout << a[i] << " "; // } // return 0; //} #include<iostream> using namespace std; #include<iostream> using namespace std; typedef long long LL; const int N = 1e5 + 10; int n, m; LL a[N], f[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; f[i] += a[i]; f[i + 1] -= a[i]; } while (m--) { int l, r, k; cin >> l >> r >> k; f[l] += k, f[r + 1] -= k; } for (int i = 1; i <= n; i++) { f[i] = f[i] + f[i - 1]; cout << f[i]<<" "; } return 0; } 2.P3406 海底高铁 - 洛谷

 

#include<iostream> using namespace std; typedef long long LL; int n, m;//n个收费点,个站 const int N = 1e3 + 10; int a[N]; LL f[N]; LL sum = 0; int main() { cin >> n >> m; int x; cin >> x; for (int i = 2; i <= m; i++) { int y; cin >> y; if (x < y) { f[x]++; f[y]--; } else if(x > y) { f[y]++; f[x]--; } x = y; } for (int i = 1; i < n; i++) { int ai, bi, ci; cin >> ai >> bi >> ci; f[i] = f[i] + f[i - 1]; sum += min(f[i] * ai, ci + f[i] * bi); } cout << sum << endl; return 0; } 3.【模板】二维差分

 

 

#include<iostream> using namespace std; typedef long long LL; int n, m, q; const int N = 1e3 + 10; LL f[N][N]; void insert(int x1, int y1, int x2, int y2, LL k) { f[x1][y1] += k; f[x2 + 1][y1] -= k; f[x1][y2 + 1] -= k; f[x2 + 1][y2 + 1] += k; } int main() { cin >> n >> m >> q; //预处理二维数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { LL x; cin >> x; //以（i,j)为左上角，(i,j)为右下脚，进行插入 insert(i, j, i, j, x); } } while (q--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; LL v; cin >> v; insert(x1, y1, x2, y2, v); } //整理合成最终矩阵，利用二维数组的前缀和 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j]; cout << f[i][j] << " "; } cout << endl; } }

利用二维查分填表

最后利用前缀和完善数组 

4.P3397 地毯 - 洛谷（第三题的模版题）

 

#include<iostream> using namespace std; typedef long long LL; int n, m; const int N = 1e3 + 10; LL f[N][N]; void insert(int x1, int y1, int x2, int y2, LL k) { f[x1][y1] += k; f[x2 + 1][y1] -= k; f[x1][y2 + 1] -= k; f[x2 + 1][y2 + 1] += k; } int main() { cin >> n >> m; //预处理二维数组 while (m--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; insert(x1, y1, x2, y2, 1); } //整理合成最终矩阵，利用二维数组的前缀和 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j]; cout << f[i][j] << " "; } cout << endl; } }