202109-2-非零段划分

/* CCF202109-2 非零段划分 */

#include <iostream>

#include <stdio.h>

#include <algorithm>

#define aaa

using namespace std;

const int N = 500000;

const int M = 10000;

int a[N + 2], d[M + 1];

/*

* 这里还需要注意的是：是假设水从上面下降，逐渐显现出山峰；而不是水位逐渐升高，淹没山峰

* 因为用下降来处理的话，最后才计算的 0 是可以不考虑的。（求前缀和时最后计算的 0）

* 如果用水位上升来处理，不能不考虑 0？

* 

* 因为题意的关系，是小于 p 的置为 0，而在求算时 p 的取值是数组中的某个数，

* 在水位上升时，p 取到山峰时，非零段的数目是不变的；p 大于山谷一个 1 的时候，非零段的数目才增 1

* 上升关系不能用差分来做

*/

int main()

{

#ifdef aaa

    freopen("stdin.txt", "r", stdin);

#endif // aaa

    int n;

    scanf("%d", &n);

    // 开始位置为 1 上

    for (int i = 1; i <= n; i++) 

        scanf("%d", &a[i]);

    a[0] = a[n + 1] = 0;

    //a+n+2 中的 2 是因为上面设置了 a [0] = a [n + 1] = 0，

    // 最后还要再减去 1 是因为 a [0] 么？那最终的 n 代表的意义是什么？

    //unique (a, a + n + 2) - a 表示去重后的数组的元素个数（设为 m，则 a 数组下标取到的最大值为 m-1，查看下面的 i+1 的最大值即是这个），因为在下面的 for 循环中用到了 i+1，

    //i+1<unique (a, a + n + 2) - a，即 i<unique (a, a + n + 2) - a - 1

    // 故 n 的取值如此

    n = unique(a, a + n + 2) - a - 1;

    memset(d, 0, sizeof d);

    //d 数组下标的取值就是 p 值，这里是假设水从上往下下降的

    for (int i = 1; i < n; i++)

        if (a[i - 1] < a[i] && a[i] > a[i + 1]) 

            d[a[i]]++; 

            // 只有当它比两边都高的时候，当 p 取为 a [i] 时，它作为新的山峰显现出来；如果旁边有更高的，并不会出现新的山峰

        else if (a[i - 1] > a[i] && a[i] < a[i + 1]) 

            d[a[i]]--;

            // 如果 a [i] 为 0 呢？

            //a [i] 为 0 时必然会有 d [0]--，但是在下面求前缀和的时候不会用到 d [0]

    int ans = 0, sum = 0;   // 差分前缀和即为答案

    //M 为可能的最大数，水从上往下下降的

    for (int i = M; i >= 1; i--)

        sum += d[i], ans = max(ans, sum);

    printf("%d\n", ans);

    return 0;

}