好久没写过决策单调性了。
这题其实就是 $p_i=lceilmaxlimits_{j}(a_j-a_i+sqrt{|i-j|}) ceil$。
拆成两边，先只考虑 $j<i$，然后反过来再做一遍。
然后，发现满足决策单调性。怎么发现的呢？
令 $f_j(i)=sqrt{i-j}$。会发现 $f_{j_1}(i)$ 和 $f_{j_2}(i)$ 至多只有一个交点。
然后，由于这里是小取代大，所以可以用单调队列。然后发现式子里面与 $p_i$ 无关，所以转移可以按任意顺序，那就可以分治。
这里选择分治，毕竟码量小，好想。
$solve(l,r,L,R)$ 表示正在计算 $[l,r]$ 的 $p$，已知决策在 $[L,R]$ 里面。
取 $l,r$ 的中点 $mid$，求出其的决策点 $MID$。那么 $[l,mid-1]$ 的决策点肯定在 $[L,MID]$，那么可以递归 $solve(l,mid-1,L,MID)$。同理 $solve(mid+1,r,MID,R)$。
由于只会递归 $log n$ 层，每层会循环 $[L,R]$ 的并集也就是 $[1,n]$，所以复杂度是 $O(nlog n)$。
如果把 $p_i$ 存成实数，最后再取整，那么决策点可以看作是唯一的。就不会出现一些奇怪的情况……
（别问我为什么挂了那么久……）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=500050; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ int x=0,f=0;char ch=getchar(); while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int n,a[maxn]; double ans[maxn]; inline double calc(int i,int j){ return sqrt(i-j)+a[j]-a[i]; } void solve(int l,int r,int L,int R){ if(l>r) return; int mid=(l+r)>>1,p=L; FOR(i,L+1,min(mid,R)) if(calc(mid,p)<calc(mid,i)) p=i; ans[mid]=max(ans[mid],calc(mid,p)); solve(l,mid-1,L,p); solve(mid+1,r,p,R); } int main(){ n=read(); FOR(i,1,n) a[i]=read(); solve(1,n,1,n); FOR(i,1,n/2) swap(a[i],a[n-i+1]),swap(ans[i],ans[n-i+1]); solve(1,n,1,n); FOR(i,1,n/2) swap(a[i],a[n-i+1]),swap(ans[i],ans[n-i+1]); FOR(i,1,n) printf("%.0lf ",ceil(ans[i])); }