提供两种解法:

第一种:数论分块

$h_j\le h_i+p-\sqrt{|i-j|}$

$p\ge h_j-h_i+\sqrt{|i-j|}$

$\sqrt{|i-j|}$拆成$i>j,i<j$两个部分进行处理。

由于$p$为整数,那么$w<\sqrt{|i-j|}<w+1$的情况,

$\sqrt{|i-j|}$一律当成$w+1$处理,也就是在处理的过程中,需要枚举$w$的取值,以及它的范围。

然后用$ST$表找出范围内最大的$h_j$,即可用$\Theta(n\sqrt{n}+n\log n)$的时间勉强卡过此题。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
#define eps 1e-8
using namespace std;
const int N=1e5+5;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int ans[N],f[18][N],lg[N],n;
I int query(int x,int y){int k=lg[y-x+1];return max(f[k][x],f[k][y-(1<<k)+1]);}
int main()
{
    qr(n);
    for(int i=1;i<=n;i++)qr(f[0][i]);
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=lg[n];i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    for(int i=1;i<=n;i++)
        for(int l=i+1,r,j=1;l<=n;l=r+1,j++)
            r=min(n,i+j*j),ans[i]=max(ans[i],query(l,r)-f[0][i]+j);
    for(int i=n;i;i--)
        for(int r=i-1,l,j=1;r>=1;r=l-1,j++)
            l=max(1,i-j*j),ans[i]=max(ans[i],query(l,r)-f[0][i]+j);
    for(int i=1;i<=n;i++)
        qw(ans[i]),puts("");
    return 0;
}

第二种:不等式决策单调性

把$h_j+\sqrt{i-j}$单独拿出来分析。

设$f_j(i)=h_j+\sqrt{i-j}$,显然这个函数是单调递增的,且增长速度由$\sqrt{i-j}$逐渐减慢。

对于$j_1,j_2(j_1<j_2)$,显然存在一个临界点使得$f_{j_1}(k)=f_{j_2}(k)$,之后$f_{j_1}(i)<f_{j_2}(i)(i>k)$,

证明可以独立完成。

把这样的临界点称为$k_{j_1,j_2}$。

我们维护一个$k_{j_1,j_2}<k_{j_2,j_3}$的决策单调队列。

因为$k_{j_1,j_2}\ge k_{j_2,j_3}$的话,$j_2$对答案完全没有贡献。

对于$i$的决策而言,仅需要找到$k$就好了。

然后就是确定$k_{q_r,i}$的临界值了,二分即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
#define eps 1e-8
using namespace std;
const int N=5e5+5;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
double sq[N],p[N];int a[N],q[N],k[N],n;
I double calc(const int i,const int j){return a[j]+sq[i-j];}
I double cmx(const double x,const double y){return x<y?y:x;}
int get(const int x,const int y)
{
    int l=y,r=k[x]?k[x]:n,ans=n+1;
    while(l<=r)
    {
        int mid=l+r+1>>1;
        if(calc(mid,x)<=calc(mid,y))ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
void work()
{
    for(int i=1,l=1,r=0;i<=n;i++)
    {
        while(l<r&&calc(k[r-1],q[r])<=calc(k[r-1],i))--r;
        k[r]=get(q[r],i);q[++r]=i;
        while(l<r&&k[l]<=i)++l;
        p[i]=cmx(p[i],calc(i,q[l]));
    }
}
int main()
{
    qr(n);
    for(int i=1;i<=n;i++)qr(a[i]),sq[i]=sqrt(i);
    work();
    for(int i=1,j=n;i<j;i++,j--)
        swap(a[i],a[j]),swap(p[i],p[j]);
    memset(k,0,sizeof(int)*(n+1));
    work();
    for(int i=n;i;i--)
        qw((int)ceil(p[i])-a[i]),puts("");
    return 0;
}