题解：CF2023F Hills and Pits

题目：

思路

\(\sum_{i=l}^r a_i< 0\) 时无解，下面均指有解情况。

易证 \(ans_{[l,r]}\le 2(r-l)\)，可以左右左走一遍。

\(s\)：起点。
\(t\)：终点。
下面假设 \(s<t\)，最后可以倒着再跑一遍处理 \(s>t\)。

\(l→r\)

显然的性质：能取就取，能放就放。
我们考虑假设从 \(l\) 出发向右走到 \(r\)，思考策略时可以用一下前缀和（这里的前缀和指从 \(l\) 开始的前缀和），那么如果一个点前缀和为负，则需要找到后面第一个为正的位置运回来，所以每个前缀为负的位置的边会走三次，而前缀为正的位置的边会走一次。

任取起点和终点

令 \(l\le s<t\le r\)。
显然可能作为最优的起点开始不会往右走，因为你最终必往左走，那你还不如选更右的点能省去开局往右走的路程。
终点同理。

那么我们的路径形如 \(s→l→r→t\)。
令 \(qz_i\) 为 \(\sum_{j=l}^ia_j\)。
根据上面那个证明 \(qz_s\ge 0\)。
我们发现除了一条 \(s+1→t\) 上的边其他边都是走两遍就处理好了。
\(s+1→t\) 的情况和 \(l→r\) 的思路是一样的。

---

\[ans_{[l,r]}=\min\{3\sum_{i=s}^{t-1}[qz_i<0]+\sum_{i=s}^{t-1}[qz_i\ge 0]+2((r-l)-(t-s))\} \]

trick：分离常数，配方。

\[ans_{[l,r]}=\min\{\sum_{i=s}^{t-1}[qz_i<0]-\sum_{i=s}^{t-1}[qz_i\ge 0]+2(r-l)\} \]

整理一下：

trick：系数下放到点，转化为最大子段和问题。

\[ans_{[l,r]}=2(r-l)-\max(\sum_{i=s}^{t-1}[qz_i\ge 0]-\sum_{i=s}^{t-1}[qz_i<0]) \]

---

思考如何维护下放的系数。

令 \(s_i\) 为 \(\sum_{j=1}^ia_i\)。

\[ans_{[l,r]}=2(r-l)-\max(\sum_{i=s}^{t-1}[s_i\ge s_{l-1}]-\sum_{i=s}^{t-1}[s_i<s_{l-1}]) \]

初始系数均设为 \(-1\)，询问离线从大到小枚举 \(P\) 扫描线，把 \(s_i=P\) 的 \(i\) 位置设为 \(1\)，然后处理左端点满足 \(s_{l-1}=P\) 的询问。

实际上不用离散化，可以按 \(s_i\) 从大到小扫描，把 \(s_i\) 设为 \(1\)，然后处理 \(l-1=i\) 的询问。

代码：

#include<bits/stdc++.h>
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*f;
}
#define int long long
const int QAQ=3e5+7,inf=2e9;
int t,n,q,a[QAQ],p[QAQ],qz[QAQ],ans[QAQ];
struct xxx {int l,r;} d[QAQ];
bool cmp(int a,int b)
{if(qz[a]==qz[b]) return a>b;return qz[a]>qz[b];
}
namespace xds
{struct jd {int zb,yb,zj,sum;} s[QAQ*4];jd operator +(jd a,jd b){return {max(a.zb,a.sum+b.zb),max(a.yb+b.sum,b.yb),max({a.zj,b.zj,a.yb+b.zb}),a.sum+b.sum};}#define lp (p<<1)#define rp ((p<<1)|1)void up(int p) {s[p]=s[lp]+s[rp];}void build(int p,int l,int r){if(l==r) return s[p]={0,0,0,-1},void();int mid=(l+r)>>1;build(lp,l,mid),build(rp,mid+1,r);up(p);}void gai(int p,int l,int r,int x){if(l==r) return s[p]={1,1,1,1},void();int mid=(l+r)>>1;if(x<=mid) gai(lp,l,mid,x);else gai(rp,mid+1,r,x);up(p);}jd cha(int p,int l,int r,int L,int R){if(L<=l&&r<=R) return s[p];int mid=(l+r)>>1;jd ccx={0,0,0,0},swl={0,0,0,0};if(L<=mid) ccx=cha(lp,l,mid,L,R);if(mid+1<=R) swl=cha(rp,mid+1,r,L,R);return ccx+swl;}
};
using namespace xds;
vector<int> ccx[QAQ];
void pao()
{p[0]=0;for(int i=1;i<=n;i++) ccx[i].clear(),qz[i]=qz[i-1]+a[i],p[i]=i;for(int i=1;i<=q;i++) if(d[i].l!=d[i].r) ccx[d[i].l].push_back(i);sort(p,p+n+1,cmp);build(1,1,n);for(int i=0;i<=n;i++){if(p[i]) gai(1,1,n,p[i]);for(int x:ccx[p[i]+1])ans[x]=min(ans[x],2*(d[x].r-d[x].l)-cha(1,1,n,d[x].l,d[x].r-1).zj);}
}
void chuli()
{n=read(),q=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=q;i++) d[i]={read(),read()},ans[i]=2*(d[i].r-d[i].l);pao();for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]);for(int i=1;i<=q;i++) d[i].l=n-d[i].l+1,d[i].r=n-d[i].r+1,swap(d[i].l,d[i].r);pao();for(int i=1;i<=q;i++)if(qz[d[i].r]-qz[d[i].l-1]>=0) printf("%lld\n",ans[i]);else puts("-1");
} 
signed main()
{t=read();for(int i=1;i<=t;i++) chuli();return 0;
}