为什么想到用差分(个人认为很重要)
y总讲4007. 非零段划分 - AcWing题库时并没有将题目和差分联系在一起，但在上一次ccf这道题没有做出来后，我意识到对差分的总结还不够深刻，于是进行了复盘
差分的2种应用方向
1.同时改变一个区间中数的大小
95%的差分都被应用到了这个方向，大部分人都很熟练
2.对差分数组本身意义的考察
差分数组中每个数表示：相邻两数之间的高度差，这个应用方向考察不多，相对陌生所以，难！
我是怎么注意到第二个方向的
这里要吹一下蓝书，蓝书上差分一共只有2道例题，这两道例题分别考察了这两个方向
4007. 非零段划分 - AcWing题库和本题2014. 岛 - AcWing题库其实都是101. 最高的牛 - AcWing题库的变形！！！
一维差分
| 题目链接 | 题意描述 | 题目总结 | c++题解 |
|---|---|---|---|
| 797. 差分 - AcWing题库 | 差分模板：给一个区间所有数同时加上一个数； | 差分数组的每个数的前缀和就是原数 ；所以改变差分数组的一个数，所有求前缀和时用到这个数的都会受到影响 | |
| 100. 增减序列 - AcWing题库 | 每次给任意一个区间所有数+1或者-1，求多少次操作后，所有数相等； | 本题要理解差分数组本身的含义：表示原数组中每两个相邻数的差；将原数组都变成一样等价于将差分数组下标大于1的数都变为0；所以优先选择一对(正，负)操作 | AcWing 100. IncDec序列 - AcWing |
| 101. 最高的牛 - AcWing题库 | 已知数组中的最大数，和一些数之间的关系，求原数组每个数的最大可能值 | AcWing 101. 最高的牛 - AcWing | |
| 2014. 岛 - AcWing题库 | 同理，用map离散化优化高度的枚举(高度的数据范围大) | ||
| 4007. 非零段划分 - AcWing题库 | 已知数组中的每个数的值，和数组中的最大数，求一些数之间的关系 |
说明：
本题2014. 岛 - AcWing题库实际上的考察是：水位每上涨一个高度差后对数组中数的关系有怎样的影响
与101. 最高的牛 - AcWing题库相比相当于问：水位在哪里的时候有最多的长方形可以相互看见
%%%%%%
%%%%%5
%%%
tql
tql%%%
👍👍👍❤️❤️❤️
%%% 学习了 学习了
%%%
好强啊%%%
总结的很好，感谢
感谢支持！
大佬太秀了！点赞，第二个应用的确比较少
感谢支持！
蓝书是啥
《算法竞赛进阶指南》打卡活动