题解：P12503 「ROI 2025 Day1」索契游乐园

· · 题解

不错的函数最优化练习题。考验选手卡常技巧。

首先，对于一个选手来说向左走和向右走是独立的。有两种策略，一个是向左来回走一趟然后向右，另一种是向右来回一趟再向左。直接把来回的权值设成 2w 即可。然后两种策略的答案取 \min 即可。

于是经过上述转化，我们只需要平移坐标然后考虑从 x_0=0 开始的单方向行走就行了。一个最直接的策略就是枚举走到了哪个位置 x，有一个行走的能量，w\times x，已经被覆盖的点 c_i 消耗的能量就是 \min((c_i\bmod d)^2,(c_i-c_i\bmod d)^2)，未被覆盖点消耗的能量是 (c_i-x)^2。于是答案就是

f(x)=w\times x+\sum\limits_{c_i\le x} \min((c_i\bmod d)^2,(c_i-c_i\bmod d)^2)+\sum\limits_{c_i>x}(c_i-x)^2

记录一些前后缀和可以 O(\log n) 计算这个式子，带 \log 的原因是你需要二分出 c_i\le x 的分界点 i。

这个式子是一些二次函数状物构成的，所以我们猜测其具有凸性，且是一个单谷函数。

于是可以通过直接三分来找到极值点，单次计算 f(x) 的代价为 O(n\log n)。所以总的时间复杂度就是 O(m\log n\log V)，可以喜提 87\rm pts。

发现复杂度的瓶颈是在于每次三分内部要要二分出是在哪一段。于是我们可以先三分出在哪一段，然后段内再三分出哪个是极值点，这样子第一次计算的时候取点我们直接取段内的左右端点即可，第二次计算的时候已经确定段了就不需要再二分段了。时间复杂度也可以做到 O(m(\log n+\log V))，可以获得 91 \rm pts。

不过其实最后确定段之后，其中一个变量分界点 i 已经确定了，于是这就是一个纯的二次函数，我们可以直接求出二次函数极值点，然后在附近找到 d 的倍数看看谁最优即可（注意特判二次项系数为 0）。于是又优化掉一个 \log V。时间复杂度 O(m\log n)，还是 91\rm pts。

其实整数域的三分是可以用二分替代的，因为下凸函数满足差分单调递增，我们直接二分出差分值在 0 附近的点即可。这样子能大幅度减少常数，获得 100 \rm pts。

当然由于我的写法比较丑陋，所以还需要加入下面若干常数优化。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int maxn=3e5+10;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct Calc{
    int c[maxn],to[maxn],p[maxn],n,m,d,W,R,lst[3];
    i128 pre[maxn],s1[maxn],s2[maxn],v1[maxn],v2[maxn]; int id;
    ll V(ll x){ return x*x; }
    inline i128 f(ll x){ return W*x/d+pre[id]+s2[id+1]-2*x*s1[id+1]+(i128)(n-id)*x*x; }
    inline i128 g(int z){
        ll x1=p[z],x2=p[z+1]-d;
        if(x1==x2) return W*x1/d+v1[z];
        return min(W*x1/d+v1[z],W*x2/d+v2[z]);
    }
    inline void G(int z){
        ll x1=p[z],x2=p[z+1]-d;
        v1[z]=pre[to[z]]+s2[to[z]+1]-2*x1*s1[to[z]+1]+(i128)(n-to[z])*x1*x1;
        v2[z]=pre[to[z]]+s2[to[z]+1]-2*x2*s1[to[z]+1]+(i128)(n-to[z])*x2*x2;
    }
    void init(){
        sort(c+1,c+1+n); m=0; c[n+1]=2e9;
        if(c[1]){ p[++m]=0; to[m]=0; }// p:坐标 to:覆盖了前缀哪些位置 
        for(int i=1;i<=n;i++){
            int z=c[i]%d==0?c[i]:c[i]+d-c[i]%d;
            if(z<c[i+1]) p[++m]=z,to[m]=i;
            pre[i]=pre[i-1]+V(min(c[i]%d,d-c[i]%d));
        } 
        p[m+1]=p[m]+d; lst[1]=lst[2]=m-1;
        for(int i=n;i>=1;i--) s1[i]=s1[i+1]+c[i],s2[i]=s2[i+1]+V(c[i]);
        for(int i=1;i<=m;i++) G(i);
    }
    ll calc(int w,int t){
        if(m==1) return 0; 
        W=w; int l=1,r=min(lst[t],m-1);
        while(l<r){
            int mid=(l+r)>>1;
            if(g(mid)-g(mid+1)<=0) r=mid;
            else l=mid+1;
        }
        int id2=g(l)<g(l+1)?l:l+1; lst[t]=id2; 
        l=p[id2]; r=p[id2+1]-d; id=to[id2];
        i128 ans=min(f(l),f(r));
        if(n!=id){
            i128 x1=(2*d*s1[id+1]-W)/2/d/(n-id);
            ll v1=x1+d-x1%d,v2=x1-x1%d;
            if(l<=v1&&v1<=r) ans=min(ans,f(v1));
            if(l<=v2&&v2<=r) ans=min(ans,f(v2));
        }
        return (ll)ans;
    }
}L,R;
int n,m,a[maxn],x0; ll ans[maxn<<1];
vector<pair<int,int> > Q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=read();
    cin>>x0>>L.d; R.d=L.d;
    for(int i=1;i<=n;i++)
        if(a[i]<=x0) L.c[++L.n]=x0-a[i];
        else R.c[++R.n]=a[i]-x0;
    cin>>m; L.init(); R.init();
    for(int i=1;i<=m;i++) Q.pb(read(),i);
    sort(Q.begin(),Q.end());
    for(auto z:Q) ans[z.se]=min(L.calc(z.fi,1)+R.calc(2*z.fi,2),L.calc(2*z.fi,2)+R.calc(z.fi,1));
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}