分析

读完题，我们发现为了满足所有节点 。通过不等式变形 。那么我们就有了 的做法，是过不了的，所以必须优化，我们现在为了去掉绝对值符号，所以考虑从左到右和从右到左分别进行一次转移。令 。那么，根据 的函数图像非常容易得到

那么满足这个式子的，我们直接通过决策单调性优化就好了，时间复杂度为 ，在 上还有一个加强版 。卡掉了分块+rmq的做法。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10,inf = 2e9;
int ans[2][N],h[N],n;
int read() {
    int x=0;char ch = getchar();
    while(!isdigit(ch)) {ch = getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x;    
}
void solve(int l,int r,int vl,int vr,int opt) {
    int mid = l + r >> 1;
    double Max = -2e9;int pos = 0;
    for(int p = vl;p <= mid && p <= vr;p++) {
        double val = h[p] - h[mid] + sqrt(mid - p);
        if(val > Max) {
            pos = p;Max = val;
        }
    }
    ans[opt][mid] = ceil(Max);
    if(l <= mid - 1) solve(l,mid-1,vl,pos,opt);
    if(mid + 1 <= r) solve(mid+1,r,pos,vr,opt);
}
int main() {
    n = read();
    for(int i = 1;i <= n;i++) h[i] = read();
    solve(1,n,1,n,0);
    reverse(h+1,h+1+n);
    solve(1,n,1,n,1);
    reverse(ans[1]+1,ans[1]+1+n);
    for(int i = 1;i <= n;i++) {
        printf("%d\n",max(ans[1][i],ans[0][i]) );
    }
}