O(n)线性做法

闲话

不知道出题人的 $O(n \log n)$ 是怎么想的，稍微处理下就是线性了，爆标了。

正文

本质这种问题我们显然考虑考虑钦定最大值，建一颗笛卡尔树，两个数值相同取标号较小的那一个，然后跑笛卡尔树上分治检查所有区间。

假设目前分治中心为 $u$，在区间包含 $u$ 的前提下，$u$ 左边接一段后缀、右边接一段前缀，这两段加起来的最大可能贡献必须都不为正，否则把那段接上就能让区间和超过 $a_u$。

于是只要对树上每个节点 $u$ 检查两件事即可：

• $u$ 的左子树对应的那一段整体就在 $u$ 左边，若左子树的最大后缀和大于 $0$，则取这段后缀加上 $a_u$ 会违反。
• $u$ 的右子树对应的那一段整体就在 $u$ 右边，若右子树的最大前缀和大于 $0$，则取 $a_u$ 加上这段前缀会违反。
  两边都不大于 $0$ 时，任何包含 $u$ 的区间和都不会超过 $a_u$。

dp 的转移是平凡的，可以理解是二叉树上维护前后缀最大子段和，只需要考虑取不取 $a_u$ 和对于另一边子树的贡献即可，和线段树维护最大子段和的做法是一模一样的（本质上这个东西具有结合律，线段树也只是二叉树的一种，不过是一颗完全二叉树而已。）

时间复杂度 $O(n)$，只需要使用笛卡尔树和比较简单的 dp。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
const int N=5e5+5,inf=(1LL<<62);
int n,t,a[N],st[N],flag,len,b[N],top,ls[N],rs[N],f[N],suf[N],pre[N],sum[N],rt;

void dfs(int u){
	if(ls[u])dfs(ls[u]);
	if(rs[u])dfs(rs[u]);
	if(ls[u]&&suf[ls[u]]>0)flag=0;
	if(rs[u]&&pre[rs[u]]>0)flag=0;
	sum[u]=sum[ls[u]]+sum[rs[u]]+a[u];
	int pl=(ls[u]?pre[ls[u]]:-inf),pr=(rs[u]?suf[rs[u]]:-inf);
	int sl=(ls[u]?max(0LL,suf[ls[u]]):0),sr=(rs[u]?max(0LL,pre[rs[u]]):0);
	pre[u]=max(pl,sum[ls[u]]+a[u]+sr);
	suf[u]=max(pr,sum[rs[u]]+a[u]+sl);
}

void work(){
	cin >> n;top=0;sum[0]=0;flag=1;
	for(int i= 1;i <= n;i++)cin >> a[i],ls[i]=rs[i]=f[i]=pre[i]=suf[i]=sum[i]=0;
	for(int i = 1;i <= n;i++){
		int last = 0;
		while(top&&a[st[top]]<a[i])last=st[top--];
		if(top)f[i]=st[top],rs[st[top]]=i;
		if(last)ls[i]=last,f[last]=i;
		st[++top]=i;
	}
	rt=st[1];
	while(f[rt])rt=f[rt];
	dfs(rt);
	cout << (flag?"YES\n":"NO\n");
}

signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> t;
	while(t--)work();
	return 0;
}