AcWing 4738. 快乐子数组
原题链接
中等
作者:
我独自退化
,
2023-11-28 01:11:33
,
所有人可见
,
阅读 65
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+1;
int t;
int main()
{
cin>>t;
for(int j=1;j<=t;j++)
{
long p[N],r[N];
long pp[N];
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&p[i]);
p[i]+=p[i-1];
pp[i]=pp[i-1]+p[i];
}
int stk[N],tt=0;
p[n+1]=-1e9;
stk[tt]=n+1;
for(int i=n;i>=0;i--)
{
while(tt>=0&&p[stk[tt]]>=p[i])
tt--;
// if(tt==0)
// r[i+1]=i+1;
// else
r[i+1]=stk[tt]-1;
stk[++tt]=i;
}
// for(int i=1;i<=n;i++)
// cout<<p[i]<<' ';
// puts(" ");
// for(int i=1;i<=n;i++)
// cout<<pp[i]<<' ';
// puts(" ");
long long sum=0;
for(int i=1;i<=n;i++)
sum+=pp[r[i]]-pp[i-1]-(r[i]-i+1)*p[i-1];
printf("Case #%d: %lld\n",j,sum);
}
return 0;
}
//pp[r[l]]-pp[l-1]-(r[l]-l+1)*(p[l-1])