P11953 [科大国创杯初中组 2023] 石子题解

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 （如线段树）里即可，移动时修改。

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

CPP

#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;
}

P11953 [科大国创杯初中组 2023] 石子题解

文章操作

相关推荐

评论

P11953 [科大国创杯初中组 2023] 石子题解