自动搬运

查看原文

来自洛谷，原作者为

	huangleyi0129 Keep dreaming, remain loving.

搬运于2025-08-24 23:11:36，当前版本为作者最后更新于2025-05-02 20:56:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$O(n^2)$ 的区间 DP 是显然的，但似乎是场上的最高分。

DP 是没有前途的，我们贪心地考虑该问题。

设起点为 $x$，先考虑一种特殊情况，即 $x$ 左边单调递减，右边单调递增。

此时显然可以直接贪心选较小的，很好做，故考虑将原问题转化至此情况。

将一个区间的点抽象成块，考虑调整左右两个块的顺序会如何。

令 $\Delta ans=len_2S_1-len_1S_2\le 0$，即 $\overline{a_1}=\frac{S_1}{len_1}\le\frac{S_2}{len_2}=\overline{a_2}$。

即一般地，先处理平均值较小的块。

所以，以 $i$ 启的向右的块一定延申至 $j$，使得 $\overline{a}$ 最小（向左同理），计算的时间复杂度为均摊 $O(n)$。

这样，我们就有了一个单点 $O(n)$ 的做法。

由于数据随机，所以做法其实是单点 $O(\log n)$，总 $O(n\log n)$ 的。

如果不随机，我们发现答案只与 $x$ 两边块的状态（如 $len$，$S$，$\sum ia_i$，etc. ）与它们平均值的顺序有关，离散化后扔进 DS （如线段树）里即可，移动时修改。

贴一下保证随机的代码（目前最优解）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
int a[N],f[N],g[N],n,l,r;
ll s[N],s2[N];
ll S(const int l,const int r)
{
	return s[r]-s[l-1];
}
ll cost(const int x,const int dir,const int t)
{
	int r=dir?g[x]:f[x];
	if(dir==1)
		return (t+x)*S(x,r)-(s2[r]-s2[x-1]);
	else
		return (t-x)*S(r,x)+s2[x]-s2[r-1];
}
void init()
{
	int x;
	f[1]=1;
	for(int i=2;i<=n;++i)
	{
		f[i]=i,x=i-1;
		while(x>0&&(i-f[i]+1)*S(f[x],x)<=(x+1-f[x])*S(f[i],i))
			f[i]=f[x],x=f[x]-1;
	}
	g[n]=n;
	for(int i=n-1;i>=1;--i)
	{
		g[i]=i,x=i+1;
		while(x<=n&&(g[i]-i+1)*S(x,g[x])<=(g[x]-x+1)*S(i,g[i]))
			g[i]=g[x],x=g[x]+1;
	}
}
void solve(const int s)
{
	int l=s-1,r=s+1,t=n-1;
	long long ans=(ll)(n-1)*a[s];
	while(l>0&&r<=n)
	{
		if(S(f[l],l)*(g[r]-r+1)<=S(r,g[r])*(l-f[l]+1))
			ans+=cost(l,0,t),t-=(l-f[l]+1),l=f[l]-1;
		else
			ans+=cost(r,1,t),t-=(g[r]-r+1),r=g[r]+1;
	}
	while(l>0)
		ans+=cost(l,0,t),t-=(l-f[l]+1),l=f[l]-1;
	while(r<=n)
		ans+=cost(r,1,t),t-=(g[r]-r+1),r=g[r]+1;
	cout<<ans<<' ';
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>l>>r;
	for(int i=1;i<=n;++i)
		cin>>a[i],s[i]=s[i-1]+a[i],s2[i]=s2[i-1]+1LL*a[i]*i;
	init();
	for(int i=l;i<=r;++i)
		solve(i);
	return 0;
}