CSP202109-2 非零段划分

题意

给出一个非负整数组成的数组$A$，求$p$，使得将$A$中小于$p$的数置零后所含的非零段最多
数据范围：$n\le 5\times 10^5, A_i\le 10^4$

题解

1. $70\%$数据
   枚举$p$
   针对每一个$p$，计算出数组$A$的情况，进而计算非零段的个数，不断更新答案
   时间复杂度为$O(nm)$

2. $100\%$数据
   让$p$从大到小，逐渐使非零段出现
   对于数组中的山峰（$A[i-1]<A[i]>A[i+1]$）,每出现一个会使非零段多一个，贡献为$+1$
   对于数组中的山谷（$A[i-1]>A[i]<A[i+1]$）,每出现一个会使非零段少一个，贡献为$-1$
   统计每个$p$对应的山峰和山谷的贡献，并运用前缀和思想在从大到小枚举$p$的过程中求出答案
   对于可能出现的相邻重复的数，事先去重
   时间复杂度为$O(n+m)$
   代码

   #include<iostream>
   #include<cstdio>
   #include<algorithm>
   using namespace std;
   const int N=5e5+10;
   const int M=1e4;
   int n,p,s;
   int a[N],c[N];
   int main(){
       scanf("%d",&n);
       for(int i=1;i<=n;i++)
           scanf("%d",&a[i]);
       n=unique(a,a+n+2)-a;
       for(int i=1;i<n-1;i++)
           if(a[i-1]<a[i] && a[i]>a[i+1])
               c[a[i]]++;
           else if(a[i-1]>a[i] && a[i]<a[i+1])
               c[a[i]]--;
       for(int i=M;i>0;i--){
           s+=c[i];
           p=p>s?p:s;
       }
       printf("%d",p);
       return 0;
   }

3. $100\%$数据
   差分前缀和
   如果$A[i]>A[i−1]$，则当$p$取到$A[i−1]+1$到$A[i]$之间的值时，非零段多一个，贡献为$+1$
   直接统计贡献的复杂度过高，改为统计贡献的差分数组
   对差分数组求前缀和即为贡献值，在此过程中取最大值
   时间复杂度为$O(n+m)$
   代码

   #include<iostream>
   #include<cstdio>
   using namespace std;
   const int N=5e5+10;
   const int M=1e4;
   int n,p,s;
   int a[N],c[N];
   int main(){
       scanf("%d",&n);
       for(int i=1;i<=n;i++){
           scanf("%d",&a[i]);
           if(a[i]>a[i-1]){
               c[a[i-1]+1]++;
               c[a[i]+1]--;
           }
       }
       for(int i=1;i<M;i++){
           s+=c[i];
           p=p>s?p:s;
       }
       printf("%d",p);
       return 0;
   }