P11953 [科大国创杯初中组 2023] 石子 题解
huangleyi0129
·
·
题解
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;
}
```