考虑对于每个 \(i\)，算出向左扩展到 \(1\) 时向右至少和至多扩展到哪里，记为 \(minr\) 和 \(maxr\)。
那么也就是说每个 \(i\) 会对 \(minr\sim maxr\) 做出贡献，差分一下就可以了。重点是怎么计算这两个东西。
先说 \(maxr\)。如果暴力跳，过程是：先向左扩展直到不能扩展，然后再向右扩展到不能扩展。不断重复直到左边界到 \(1\) 或者两边都无法继续扩展宣告失败。
然后你想起了刚刚做完的 E1，每次扩展一定是找到一个最近的最大值，把最大值之前的都加上，再看看能不能也把这个最大值也加上。这个可以用 ST 表和二分 \(\mathcal{O}(\log V\log n)\) 解决。
具体地说，记 \(l,r\) 为当前左右边界，\(s\) 为前缀和，在向左扩展时，要找到一个最大的 \(x\) 使得 \(s_r-s_{l-1}<a_{l-1}\)，移项变为 \(s_r<a_{l-1}+s_{l-1}\)，用 ST 表维护 \(a_i+s_i\) 的最大值。二分时每次检查右区间是否符合条件，如果是则增大左边界，否则减小右边界。向右扩展基本同理，式子稍有变化，换成了维护最小值。
其实 \(maxr\) 也可以双指针来着然后再看 \(minr\)。有区别的是向右扩展时不是无脑扩展，而是扩展到刚好够左边能跨过下一个最大值。那么只需每次向右扩展之后再二分一下，尝试把 \(r\) 往回减一些。这个不需要 ST 表。
来看一下时间复杂度。每次当前区间总和因为跨过了一个最大值，所以至少增加了一倍，那么也就最多增加 \(\log V\) 次。再加上二分和枚举 \(i\) 的复杂度，总复杂度 \(\mathcal{O}(n\log n\log V)\)。
细节说多不多说少不少。
#include<bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=2e5+5;
const int inf=0x3f3f3f3f;
inline int read();
int n,m,k;int a[N];
int f[30][N],g[30][N];
int ans[N],minr[N],maxr[N],s[N];
int getmax(int x,int y){
int s=__lg(y-x+1);
return max(f[s][x],f[s][y-(1<<s)+1]);
}
int getmin(int x,int y){
int s=__lg(y-x+1);
return min(g[s][x],g[s][y-(1<<s)+1]);
}
void work(){
n=read();read();
FOR(i,1,n)a[i]=read(),s[i]=s[i-1]+a[i],ans[i]=0;
a[n+1]=0;
FOR(i,1,n)f[0][i]=a[i]+s[i],g[0][i]=s[i]-a[i+1];
for(int j=1;1<<j<=n;++j)
for(int i=1;i+(1<<j)-1<=n;++i){
f[j][i]=max(f[j-1][i],f[j-1][i+(1<<j-1)]);
g[j][i]=min(g[j-1][i],g[j-1][i+(1<<j-1)]);
}
int L,R,l,r,mid;
FOR(i,1,n){
l=i,r=i;
while(1){
bool flag=0;
L=1,R=l;
while(L<R){
mid=L+R>>1;
if(s[r]<getmax(mid,R-1))L=mid+1;
else R=mid;
}
if(l!=L)l=L,flag=1;
if(l==1||r==n)break;
L=r,R=n;
while(L<R){
mid=L+R>>1;
if(getmin(L,mid)<s[l-1])R=mid;
else L=mid+1;
}
if(r!=L){
flag=1;
int x=L;
L=r+1,R=x;
while(L<R){
mid=L+R>>1;
if(s[mid]-s[l-1]>=a[l-1])R=mid;
else L=mid+1;
}
r=R;
}
if(!flag)break;
}
if(l==1)minr[i]=r;
else minr[i]=inf;
l=i,r=i;
while(1){
bool flag=0;
L=r,R=n;
while(L<R){
mid=L+R>>1;
if(getmin(L,mid)<s[l-1])R=mid;
else L=mid+1;
}
if(r!=L)flag=1,r=R;
L=1,R=l;
while(L<R){
mid=L+R>>1;
if(s[r]<getmax(mid,R-1))L=mid+1;
else R=mid;
}
if(l!=L)l=L,flag=1;
if(!flag)break;
}
if(l==1)maxr[i]=r;
else maxr[i]=inf;
}
FOR(i,1,n)
if(maxr[i]!=inf&&minr[i]<=maxr[i])
ans[minr[i]]++,ans[maxr[i]+1]--;
FOR(i,1,n)ans[i]+=ans[i-1];
FOR(i,1,n)printf("%lld ",ans[i]);puts("");
}
signed main()
{
int T=read();
while(T--)work();
return 0;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f*x;
}