题目链接	题意描述	题目总结	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题库相比相当于问：水位在哪里的时候有最多的长方形可以相互看见

思路

设一块长方形的高度为a[i],假设水从a[i-1]涨到(下降到)a[i],意味着所有高度在a[i]—a[i-1]的长方形都会被淹没(露出来)，相当于这些长方形的高度差被抹平(产生)(对答案的贡献都减1(+1)).同时给一个区间减去(加上)一个数，用差分

4007. 非零段划分 - AcWing题库代码：

#include &lt;iostream&gt;
#include &lt;cstring&gt;
#include &lt;algorithm&gt;
using namespace std;
const int N = 500005,M = 10000;
int a[N],b[N];
int n;
int main()
{
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
        if(a[i]>a[i-1]){
            //数的大小在[a[i-1],a[i]-1]之间的所有数都+1
            b[a[i-1]]++,b[a[i]]--;
        }
    }
    int sum = 0 ;
    for (int i = 0; i <= M; i ++ ){
        sum+=b[i];
        res = max(res,sum);
    }
    cout << res;
}

题解

对比4007. 非零段划分 - AcWing题库发现高度的数据范围比数量大的多余数想到了用map离散化(不能用unordered_map，unordered_map无法用来求前缀和)

代码：

#include &lt;iostream&gt;
#include &lt;cstring&gt;
#include &lt;algorithm&gt;
#include &lt;map&gt;


typedef long long LL;

using namespace std;
const int N = 100005,M = 1e9+1;
int a[N];
map&lt;int ,int &gt;b;
int n;
int main()
{
    cin >> n;
   
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
        if(a[i]>a[i-1]){
            //数的大小在[a[i-1],a[i]-1]之间的所有数大小都-1
            b[a[i-1]]++,b[a[i]]--;
        }
    }
    LL sum = 0 ,res = 0;
    for (auto i:b ){
        //求前缀和
        sum+=i.second;
        res = max(res,sum);
    }
    cout << res;
}