🏝️专栏： 【蓝桥杯备篇】
🌅主页： f狐o狸x

“OJ超时不是终点，是算法在提醒你该优化时间复杂度了！”

---

目录

3.25 差分数组

一、一维差分

        题目链接：

        题目描述：

        解题思路：

        解题代码：

二、海底高铁

        题目链接：

        题目描述：

        解题思路：

        解题代码：

三、二维差分

        题目链接：

        题目描述：

        解题思路：

        解题代码：

四、地毯

        题目链接：

        题目描述：

        解题思路：

        解题代码：

---

3.25 差分数组

        我们直接用一道题来了解差分数组吧

一、一维差分

        题目链接：

        【模板】差分

        题目描述：

        解题思路：

        还是可以用暴力枚举来搞定，我们把整个数组遍历一遍，再把对应位置加上x就行了，但是这样绝对是会超时长滴，不然我干嘛用这个例题？

        对于类似的题，我们就可以用差分算法，和前缀和数组类似，我们需要预处理一个差分数组出来

        这个数组的好处就是当你要在 l ~ r 的区间加上 x 的时候（图中用2~5）来表示，就只需要在差分数组中的 l 位置加上 x ，r + 1 位置减去 x ，再还原为原数组就行

         也就是：a[ l ] += x; a[ r + 1 ] -= x;

        此时还有人要问：煮波煮波，那怎么还原数组呢？其实把差分数组做一个前缀和运算即可还原 证明如下：

        解题代码：

#include <iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];int n, m;int main()
{cin >> n >> m;// 利用差分的性质预处理差分数组for(int i = 1; i <= n; i++){LL x;cin >> x;a[i] += x;a[i + 1] -= x;}// m次操作while(m--){LL l, r, x; cin >> l >> r >> x;a[l] += x;a[r + 1] -= x;}// 利用前缀和还原数组for(int i = 1; i <= n; i++){a[i] = a[i - 1] + a[i];cout << a[i] << " ";}return 0;
}

二、海底高铁

        题目链接：

        P3406 海底高铁

        题目描述：

        解题思路：

        这里我们只需要知道这个人每段铁路一共坐了几次，再判断是直接买票划算还是买卡划算，最后累加输出即可

        解题代码：

#include <iostream>using namespace std;const int N = 1e5 + 10;typedef long long LL;LL f[N];int n, m;int main()
{cin >> n >> m;int l, r; cin >> l;// 利用差分记录每段铁路经过的次数for (int i = 2; i <= m; i++){cin >> r;if (l <= r) f[l] += 1, f[r] -= 1;else f[r] += 1, f[l] -= 1;l = r;}// 还原数组for (int i = 1; i <= n; i++){f[i] = f[i - 1] + f[i];}LL ret = 0;for(int i = 1; i < n; i++){LL a, b, c; cin >> a >> b >> c;ret += min(a * f[i], c + b * f[i]);}cout << ret << endl;return 0;
}

三、二维差分

        题目链接：

        【模板】二维差分

        题目描述：

        解题思路：

        如图所示我们需要对以下结果数组进行操作：

f[x1][y1] + k

f[x2 + 1][y1] - k

f[x1][y2 + 1] - k

f[x2 + 1][y2 + 1] - k

         这样我们累加起来以后就可以得到二维数组中区间+k的操作

        解题代码：

#include <iostream>using namespace std;typedef long long LL;const int N = 1010;LL f[N][N];int n, m, q;void insert(int x1, int y1, int x2, int y2, int x)
{f[x1][y1] += x;f[x2 + 1][y1] -= x;f[x1][y2 + 1] -= x;f[x2 + 1][y2 + 1] += x;
}int main()
{cin >> n >> m >> q;// 预处理二维齐差分数组for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){LL a; cin >> a;insert(i, j, i , j ,a);}    }while(q--){LL x1, y1, x2, y2, a; cin >> x1 >> y1 >> x2 >> y2 >>a;insert(x1, y1, x2, y2, a);}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;}return 0;
}

四、地毯

        题目链接：

        P3397 地毯

        题目描述：

        

        解题思路：

        这题其实就是把地毯对应的区域全加上一，最后再输出数组即可解决

        解题代码：
 

#include <iostream>using namespace std;const int N = 1010;int f[N][N];int n, m;void insert(int x1, int y1, int x2, int y2, int a)
{f[x1][y1] += a;f[x2 + 1][y1] -= a;f[x1][y2 + 1] -= a;f[x2 + 1][y2 + 1] += a;
}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;}return 0;
}

        今天就到这里吧，下一期我们将讲解二分算法~886~

        蓝桥杯选手日常：
        睡醒→看题→看不懂→搜题解→抄代码→被卡常→怒删重写→提交→WA