题解：P11677 [USACO25JAN] Shock Wave P

· · 题解

首先各种 DP 都没有任何前途。

考虑分析性质减少不必要的操作，对于一个操作 i，肯定不能断言它能够被其他操作替代，考虑分析两个操作 i,j，发现将操作 i,j 替换为操作 1,n 一定更优。

因此我们最后肯定是先操作若干次 1，再操作若干次 n，最后操作一次 m\ (2\leq m\leq n-1)。

考虑二分只操作 1,n 的最小操作次数 ans，然后检查 ans-1 是否可行。

设 1 操作了 a 次，n 操作了 b 次，不妨设 2i\leq n（2i>n 同理），有如下式子：

p_i\leq a(i-1)+b(n-i)

强行提取 ans 的表达式 a+b。

p_i\leq (a+b)(i-1)+b(n-2i+1) \\ b\geq \frac{p_i-(a+b)(i-1)}{n-2i+1}

当 2i>n 时，同理可得：

a\geq \frac{p_i-(a+b)(n-i)}{2i-n+1}

因此，只需满足 \max \frac{p_i-(a+b)(i-1)}{n-2i+1}+\max \frac{p_i-(a+b)(n-i)}{2i-n+1}\leq a+b 即可。

因此我们可以轻松求得 ans，检查 ans-1 时，我们的式子又多出了一部分。（2i>n 的情况略）

\exist 2\leq m\leq n-1,\max \frac{p_i-(a+b)(i-1)-|m-i|}{n-2i+1}+\max \dots \leq a+b

我们希望对所有 m 维护一坨式子的最大值。

考虑这个式子的变化次数，\frac{|m-i|}{n-2i+1} 只会变化不超过 \frac{n}{n-2i+1} 次，因此总变化量是调和级数的。

实现方面，我们只关心最大的 \frac{p_i-(a+b)(i-1)-|m-i|}{n-2i+1}，考虑让最大值递减，利用可删堆的思想，每次保证最大值更新即可。由于 a,b\geq 0，我们不用处理任何式子是负数的情况。

必须要满足最大值递减才能保证优先队列做法正确，而 m 增加时只保证 i<m 的最大值递减，因此需要先从小到大枚举 m，再从大到小枚举 m，做两遍。

做两遍的时候需要控制优先队列中只保留 i>m 或 i<m 的数，因为多余的数可能无法更新到其本身的最大值，影响答案。

复杂度 O(T(n\log V+n\log^2n))。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p[100005];
bool ck(int ans){
    int blim=0,alim=0,rlim=0;
    for(int i=1;i<=n;i++){
        if(i<=n/2){
            blim=max((__int128)blim,((__int128)p[i]-(__int128)ans*(i-1)+n-2*i)/(__int128)(n-2*i+1));
        }else{
            if(2*i-n-1==0){
                rlim=max(rlim,(p[i]+i-2)/(i-1));
                continue;
            }
            alim=max((__int128)alim,((__int128)p[i]-(__int128)ans*(n-i)+2*i-n-2)/(__int128)(2*i-n-1));
        }
    }
    return alim+blim<=ans&&rlim<=ans;
}
struct node{
    int m,val,i;
    bool operator<(const node &b) const{
        return val<b.val;
    }
};
int lima[100005],limb[100005];
int calca(int ans,int i,int m){
    return ((__int128)p[i]-(__int128)ans*(n-i)+2*i-n-2-abs(m-i))/(__int128)(2*i-n-1);
}
int calcb(int ans,int i,int m){
    return ((__int128)p[i]-(__int128)ans*(i-1)+n-2*i-abs(m-i))/(__int128)(n-2*i+1);
}
bool fullchk(int ans){
    for(int i=1;i<=n;i++) lima[i]=limb[i]=0;
    priority_queue<node> Qb,Qa;
    int nowm=n;
    do{
        while(!Qa.empty()&&Qa.top().m!=nowm&&Qa.top().val!=calca(ans,Qa.top().i,nowm)){
            auto x=Qa.top();
            Qa.pop();
            x.m=nowm;
            x.val=calca(ans,x.i,nowm);
            Qa.push(x);
        }
        while(!Qb.empty()&&Qb.top().m!=nowm&&Qb.top().val!=calcb(ans,Qb.top().i,nowm)){
            auto x=Qb.top();
            Qb.pop();
            x.m=nowm;
            x.val=calcb(ans,x.i,nowm);
            Qb.push(x);
        }
        if(2*nowm-n-1!=0){
            if(nowm<=n/2){
                Qb.push({nowm,calcb(ans,nowm,nowm),nowm});
            }else{
                Qa.push({nowm,calca(ans,nowm,nowm),nowm});
            }
        }
        if(!Qa.empty()) lima[nowm]=Qa.top().val;
        if(!Qb.empty()) limb[nowm]=Qb.top().val;
    }while(nowm--);
    nowm=1;
    while(!Qa.empty()) Qa.pop();
    while(!Qb.empty()) Qb.pop();
    do{
        while(!Qa.empty()&&Qa.top().m!=nowm&&Qa.top().val!=calca(ans,Qa.top().i,nowm)){
            auto x=Qa.top();
            Qa.pop();
            x.m=nowm;
            x.val=calca(ans,x.i,nowm);
            Qa.push(x);
        }
        while(!Qb.empty()&&Qb.top().m!=nowm&&Qb.top().val!=calcb(ans,Qb.top().i,nowm)){
            auto x=Qb.top();
            Qb.pop();
            x.m=nowm;
            x.val=calcb(ans,x.i,nowm);
            Qb.push(x);
        }
        if(2*nowm-n-1!=0){
            if(nowm<=n/2){
                Qb.push({nowm,calcb(ans,nowm,nowm),nowm});
            }else{
                Qa.push({nowm,calca(ans,nowm,nowm),nowm});
            }
        }
        if(!Qa.empty()) lima[nowm]=max(lima[nowm],Qa.top().val);
        if(!Qb.empty()) limb[nowm]=max(limb[nowm],Qb.top().val);
        nowm++;
    }while(nowm<=n);
    for(int i=1;i<=n;i++){
        if(lima[i]+limb[i]<=ans){
            if(n%2==0) return 1;
            else if(p[(n+1)/2]<=(__int128)ans*(n-1)/2+abs(i-(n+1)/2)) return 1;
        }
    }
    return 0;
}
void solve(){
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++) cin>>p[i],mx=max(mx,p[i]);
    if(mx==0){
        cout<<"0\n";
        return; 
    }
    int l=0,r=2e18,ans=2e18+1;
    while(l<=r){
        int mid=(l+r)/2;
        if(ck(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if(ans<=1){
        cout<<"1\n";
        return;
    }
    if(fullchk(ans-2)){
        cout<<ans-1<<"\n";
        return;
    }
    cout<<ans<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
}