D. Slime Escape
被 greedy 整破防了。
这是转换后的题面。
考虑使用调整法构造，记 2 个序列分别为 \(f,g\)，那么一种调整法是，\(f\) 加了没事就加了不管，否则我们再考虑往当前已经构造的序列的最大值的后方加一段正贡献的 \(g\)。
显然这个很对了，但有点假（
我们考虑前缀和，那么前面的要尽可能大，一个方向的一味扩展有时候可能当前没事但会导致后面出事。
那么，我们就要当前能加多大就多大，这个加是按当前 \(f\) 的正负分类的。若 \(f\) 为正，显然直接加，然后再看看 \(g\) 那边能否有正贡献。因为初始越大，所能在 \(g\) 得到的贡献期望越大。若 \(f\) 为负，我们可以看看拿当前的往 \(g\) 扩展正贡献，然后再看看能不能不出事。
然后 \(O(n^2)\) 到 \(O(n\log n)\) trick 一下二分 + ST 表就好了。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(2e5+5);
int a[N],n,p,f[N],g[N],tot1,tot2,st1[23][N],st2[23][N],stp[23][N],sum[N];
// mi:[nw2+1,i]+x>=0
// sum[j]-sum[nw2]+x>=0 sum[j] 为 min
// sum[j]>=sum[nw2]-x 前提条件。
// sum:[nw2+1,i]+x 取 max
// \max{sum[i]-sum[nw2]+x}
// 1. 二分找到最远扩展到哪里
// 2. 取扩展区间最大
int qrymi(int l,int r) {
int qwq=log2(r-l+1);
return min(st1[qwq][l],st1[qwq][r-(1<<qwq)+1]);
}
int qrymx(int l,int r) {
int qwq=log2(r-l+1);
return max(st2[qwq][l],st2[qwq][r-(1<<qwq)+1]);
}
int qrymxp(int l,int r) {
int qwq=log2(r-l+1);
if(st2[qwq][l]>=st2[qwq][r-(1<<qwq)+1]) return stp[qwq][l];
return stp[qwq][r-(1<<qwq)+1];
}
void sol() {
cin>>n>>p;
for(int i=1;i<=n;i++) cin>>a[i];
tot1=tot2=0;
for(int i=p+1;i<=n;i++) f[++tot1]=a[i];
for(int i=p-1;i>=1;i--) g[++tot2]=a[i];
for(int i=1;i<=tot2;i++) sum[i]=sum[i-1]+g[i];
for(int i=1;i<=tot2;i++) {
st1[0][i]=sum[i]; st2[0][i]=sum[i]; stp[0][i]=i;
}
for(int i=1;(1<<i)<=tot2;i++) {
for(int j=1;j+(1<<i)-1<=tot2;j++) {
st1[i][j]=min(st1[i-1][j],st1[i-1][j+(1<<(i-1))]);
st2[i][j]=max(st2[i-1][j],st2[i-1][j+(1<<(i-1))]);
if(st2[i][j]==st2[i-1][j]) stp[i][j]=stp[i-1][j];
else stp[i][j]=stp[i-1][j+(1<<(i-1))];
}
}
int res=a[p],nw1=0,nw2=0;
bool ok=1;
while(nw1<tot1) {
if(f[nw1+1]>=0) {
res+=f[nw1+1]; ++nw1;
// for(int i=nw2+1;i<=tot2;i++) {
// if(x+g[i]<0) break ;
// x+=g[i];
// if(x>mx) {
// mx=x; pos=i;
// }
// }
int x=res,mx=0,pos=0;
int l=nw2+1,r=tot2;
while(l<=r) {
int mid=(l+r)>>1;
if(qrymi(nw2+1,mid)-sum[nw2]+res>=0) l=mid+1,pos=mid;
else r=mid-1;
}
if(!pos) {
continue ;
}
mx=qrymx(nw2+1,pos)-sum[nw2]+res;
pos=qrymxp(nw2+1,pos);
if(mx>res) {
res=mx; nw2=pos;
}
} else {
int x=res,mx=0,pos=0;
int l=nw2+1,r=tot2;
while(l<=r) {
int mid=(l+r)>>1;
if(qrymi(nw2+1,mid)-sum[nw2]+res>=0) l=mid+1,pos=mid;
else r=mid-1;
}
if(!pos) {
if(res+f[nw1+1]<0) {
ok=0; break ;
}
res+=f[nw1+1]; ++nw1;
continue ;
}
mx=qrymx(nw2+1,pos)-sum[nw2]+res;
pos=qrymxp(nw2+1,pos);
if(mx>res) {
res=mx; nw2=pos;
}
if(res+f[nw1+1]<0) {
ok=0; break ;
}
res+=f[nw1+1]; ++nw1;
}
}
if(nw1!=tot1) ok=0;
if(ok) {
cout<<"YES\n"; return ;
}
tot1=tot2=0;
for(int i=p-1;i>=1;i--) f[++tot1]=a[i];
for(int i=p+1;i<=n;i++) g[++tot2]=a[i];
for(int i=1;i<=tot2;i++) sum[i]=sum[i-1]+g[i];
for(int i=1;i<=tot2;i++) {
st1[0][i]=sum[i]; st2[0][i]=sum[i]; stp[0][i]=i;
}
for(int i=1;(1<<i)<=tot2;i++) {
for(int j=1;j+(1<<i)-1<=tot2;j++) {
st1[i][j]=min(st1[i-1][j],st1[i-1][j+(1<<(i-1))]);
st2[i][j]=max(st2[i-1][j],st2[i-1][j+(1<<(i-1))]);
if(st2[i][j]==st2[i-1][j]) stp[i][j]=stp[i-1][j];
else stp[i][j]=stp[i-1][j+(1<<(i-1))];
}
}
res=a[p],nw1=0,nw2=0;
ok=1;
while(nw1<tot1) {
if(f[nw1+1]>=0) {
res+=f[nw1+1]; ++nw1;
// for(int i=nw2+1;i<=tot2;i++) {
// if(x+g[i]<0) break ;
// x+=g[i];
// if(x>mx) {
// mx=x; pos=i;
// }
// }
int x=res,mx=0,pos=0;
int l=nw2+1,r=tot2;
while(l<=r) {
int mid=(l+r)>>1;
if(qrymi(nw2+1,mid)-sum[nw2]+res>=0) l=mid+1,pos=mid;
else r=mid-1;
}
if(!pos) {
continue ;
}
mx=qrymx(nw2+1,pos)-sum[nw2]+res;
pos=qrymxp(nw2+1,pos);
if(mx>res) {
res=mx; nw2=pos;
}
} else {
int x=res,mx=0,pos=0;
int l=nw2+1,r=tot2;
while(l<=r) {
int mid=(l+r)>>1;
if(qrymi(nw2+1,mid)-sum[nw2]+res>=0) l=mid+1,pos=mid;
else r=mid-1;
}
if(!pos) {
if(res+f[nw1+1]<0) {
ok=0; break ;
}
res+=f[nw1+1]; ++nw1;
continue ;
}
mx=qrymx(nw2+1,pos)-sum[nw2]+res;
pos=qrymxp(nw2+1,pos);
if(mx>res) {
res=mx; nw2=pos;
}
if(res+f[nw1+1]<0) {
ok=0; break ;
}
res+=f[nw1+1]; ++nw1;
}
}
if(nw1!=tot1) ok=0;
if(ok) {
cout<<"YES\n"; return ;
}
cout<<"NO\n";
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) sol();
return 0;
}
/*
调整
若<0
调整前面最大的向另一端扩展最大。
*/