抛砖引玉之非零段划分

这里先来看一道CCF的题。

题目描述

A1,A2,…,An是一个由 n 个自然数（非负整数）组成的数组。我们称其中 Ai,…,Aj 是一个非零段，当且仅当以下条件同时满足：
·1≤i≤j≤n；
·对于任意的整数 k，若 i≤k≤j，则 Ak＞0；
·i=1 或 Ai-1=0；
·j=n 或 Aj+1=0。
下面展示了几个简单的例子：
·A = [3, 1, 2, 0, 0, 2, 0, 4, 5, 0, 2] 中的 4 个非零段依次为 [3, 1, 2]、[2]、[4, 5] 和 [2]；
·A = [2, 3, 1, 4, 5] 仅有 1 个非零段；
·A = [0, 0, 0] 则不含非零段（即非零段个数为 0）。
现在我们可以对数组 A 进行如下操作：任选一个正整数 p，然后将 A 中所有小于 p 的数都变为 0。试选取一个合适的 p，使得数组 A 中的非零段个数达到最大。若输入的 A 所含非零段数已达最大值，可取 p = 1，即不对 A 做任何修改。

输入格式
从标准输入读入数据。

输入的第一行包含一个正整数 n。

输入的第二行包含 n 个用空格分隔的自然数 A1, A2, … , An。

输出格式
输出到标准输出。

仅输出一个整数，表示对数组 A 进行操作后，其非零段个数能达到的最大值。

样例

样例1输入
11
3 1 2 0 0 2 0 4 5 0 2
样例1输出
5
样例1解释
p = 2 时，A = [3, 0, 2, 0, 0, 2, 0, 4, 5, 0, 2]，5 个非零段依次为 [3]、[2]、[2]、[4, 5] 和 [2]；此时非零段个数达到最大。

样例2输入
14
5 1 20 10 10 10 10 15 10 20 1 5 10 15
样例2输出
4
样例2解释
p = 12 时，A = [0, 0, 20, 0, 0, 0, 0, 15, 0, 20, 0, 0, 0, 15]，4 个非零段依次为 [20]、[15]、[20] 和 [15]；此时非零段个数达到最大。

样例3输入
3
1 0 0
样例3输出
1
样例3解释
p = 1 时，A = [1, 0, 0]，此时仅有 1 个非零段 [1]，非零段个数达到最大。

样例4输入
3
0 0 0
样例4输出
0
样例4解释
无论 p 取何值，A 都不含有非零段，故非零段个数至多为 0。

子任务

子任务
70% 的测试数据满足 n ≤ 1000；

全部的测试数据满足 n≤5×105，且数组 A 中的每一个数均不超过 104。

求解

看完以后，不难想出最简单的方法是【暴力法】

遍历所有可能的p，将小于p的数置0

求出变化后的数组的非零段数

然后取max

但是这样的算法只能得70分。

那么考虑下如何优化，不妨考虑一下该问题的子问题：给定p，求将数组A中所有小于p的数变为0后的非零段数

数组：[ 5, 1, 20, 10, 10, 10, 15, 10, 20, 1, 5, 10, 15]

给定p=12，求非零段个数。

显然，可以找到20,15,20,15这4个非零段，仔细想想我们找的过程是什么呢？

如果第一个数大于12，非零段+1，后续我们关注的其实只是{A[i], A[i+1]|A[i]<A[i+1]}这样的数值对，比如（1,20）、（10,15）、（10,20）、（1,5）、（5,10）、（10,15）

12在键值对区间中，那么就有产生一个非零段。

即遍历后续数组，只要遇到A[i]<A[i+1]且A[i]<12<A[i+1]，那么就会A[i]的右边就一定会产生一个非零段。

考虑求解的过程，是否发现能同时求多个p的非零段数？

只要遇到A[i]<A[i]+1且A[i]<12<A[i+1]，例如10,15，那么p取11,12,13,14，15时，都能增加一个非零段。

这样如果我们用一个数组num[p]，来记录p的非零段和，是不是遍历一次原数组就能解决问题了呢？

#include <iostream>
using namespace std;
const int N = 1e6;
int dif[N], a[N];
int num[N];
int n;
void add(int l, int r) { 
    // TODO num[N]数组下标从l~r的数都+1
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i - 1] < a[i]) {
            add(a[i - 1] + 1, a[i]);
        }
    }
    // TODO 求出num[N]中的最大值，就是最大非零段和
    return 0;
}

差分数组

这里就引入今天的主角【差分数组】

定义

原数组arr（首位补0）

类型
index	1	2	3	4	5	6	7
arr	2	5	4	9	7	10	0
dif	2	3	-1	5	-2	3	-10

差分数组dif，即dif[0]=0，dif[i]=dif[i]-dif[i-1]

差分数组的特性

如果需要对L~R范围内所有数都进行相同的操作（加x或者减x），只需要在差分数组d中改变L和R+1的值即可。

例如将上述数组下标1~4的数都加1，即变成3,6,5,10

那么前缀和数组下标1~5的数变成3,3,-1,5,-3，即d[1]=d[1]+1，d[5]=d[5]-1;
查询arr数组中某个位置的数时，根据差分数组从前往后求前缀和。

再回首

上面的代码是否出现了对L~R范围内所有数都进行相同的操作呢？

1
2
3

void add(int l, int r) { 
    // TODO num[N]数组下标从l~r的数都+1
}

显然，这里就可以用差分数组优化计算过程，并且并不影响我们最后求最大值。

下面是最终的代码。

#include <iostream>
using namespace std;
const int N = 1e6;
int dif[N], a[N];
int n;
void add(int l, int r) { dif[l]++, dif[r + 1]--; }
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i - 1] < a[i]) {
            add(a[i - 1] + 1, a[i]);
        }
    }
    int maxn = 0, pre = 0;
    for (int p = 1; p < 1e4; p++) {
        pre += dif[p];
        maxn = max(maxn, pre);
    }
    cout << maxn;
    return 0;
}

不忘初心

差分数组和非零段划分

抛砖引玉之非零段划分

题目描述

样例

子任务

求解

差分数组

定义

差分数组的特性

再回首