倍增好题,赛时没想出来只写了暴力,赛后想了1h才想出来正解。
简化一下题意,这题求的是任何前缀和都非负的最长连续子序列长度。
首先我们可以想到二分,因为答案具有单调性。我们可以二分答案长度。
解释一下为什么答案具有单调性。假设我们找到一个区间 $[l,r]$ 是符合条件的,那么它满足任意前缀和非负,即 $a_l+a_{l+1}+…+a_k\geq0(l\le k\le r)$。当 $[l,r]$ 满足条件时,$[l,r-1]$ 也满足条件,因为 $[l,r-1]$ 的任意前缀也同时是 $[l,r]$。由此可知如果 $x$ 满足条件,则比 $x$ 小的都满足条件,答案具有单调性。
接下来考虑如何判断序列是否满足条件。假设我们要判断的区间是 $[l,r]$,再假设 $b$ 数组为 $a$ 数组的前缀和数组。如果 $[l,r]$ 满足条件,那么一定满足 $b_k\geq b_{l-1}(l\le k\le r)$。因为 $[l,k]$ 为 $[l,r]$ 的前缀,而这段前缀的和为 $b_k-b_{l-1}$,如果满足条件,那么 $[l,r]$ 任意前缀非负,所以 $b_k-b_{l-1}$ 非负,即 $b_k\geq b_{l-1}$。由于数据范围较大,我们的 check
函数必须是 $O(n)$ 的,而且 check
必须要枚举所有长度为 $x$ 的区间,枚举区间时间复杂度为 $O(n)$,所以我们要 $O(1)$ 求出某段区间的前缀和数组元素是否全部大于前缀和数组左端点的前一个元素。这时我们可以想到如果 $b_l\sim b_r$ 全部 $\geq b_{l-1}$,那么 $b_l\sim b_r$ 的最小值一定 $\geq b_{l-1}$。如何 $O(1)$ 地求一段区间的最小值?倍增。
时间复杂度 $O(nlogn)$。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200100,LG=20;
int g,n,s,a[N],lg[N],st[N][LG],l,r,mid;
bool check(int x)
{
int mi;
for(int i=1,j=x;j<=n;i++,j++)
{
mi=min(st[i][lg[x]],st[j-(1<<lg[x])+1][lg[x]]);//前缀和数组l~r的最小值
//printf("%d %d %d %d\n",i,j,mi+s,a[i-1]);
if(mi+s>=a[i-1]) return true;//发现长度x时有满足条件的,直接返回
}
return false;
}
int main()
{
//freopen("4.in","r",stdin);
scanf("%d",&g);
for(int i=2;i<=200000;i++) lg[i]=lg[i/2]+1;//预处理log
while(g--)
{
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]+=a[i-1];//求前缀和
}
for(int i=0;i<=lg[n];i++)//求st表
{
for(int j=1;j+(1<<i)-1<=n;j++)
{
if(!i) st[j][i]=a[j];
else st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
l=0,r=n+1;
while(l+1<r)//二分答案
{
//printf("%d %d\n",l,r);
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
if(!l) l=-1;
printf("%d\n",l);
//cout<<check(2);
}
return 0;
}