题外话，以后正经题解放洛谷上，贺题记录这种放博客园吧。
学习自 AThousandSuns 大佬的博客。
题意
给定长度为 \(n\) 的数组 \(h\) ，对于每一个 \(i\) 求出 \(p_i\) 使满足： \(\forall j,h_j \le h_i + p_i - \sqrt{\left | i - j \right | }\) 。
题解
直接把小于等于号换成等号，自信点，这样就是最优的。再进行一些移项，把 \(p_i\) 整理出来，就可以得到一下的式子：
拆掉绝对值，先只考虑 \(j < i\) 的情况，然后翻转数组再做一遍。
接下来就觉得做不下去了，我们怎么能想到决策单调性的思路呢？
关注到式子中有一个 \(\sqrt{i - j}\) ，令 \(f_j(i) = \sqrt{i - j}\) ，然后画个图啥的你就会惊奇地发现根号的函数至多只有一个交点，也就是 \(f_{j_1}(i)\) 和 \(f_{j_2}(i)\) 至多有一个交点！
因为我们是以小取大，也就是用更早的值进行决策，所以可以使用单调队列。因为式子是与 \(p_i\) 无关的，所以转移可以按任意顺序进行转移，那么我们就可以进行分治。分治的优点就在于码量小好想，就是有点局限。
定义 \(\texttt{solve(l,r,L,R)}\) 表示正在计算区间 \([l,r]\) 的 \(p\) 值，并且已知决策点就在 \([L,R]\) 中。
取 \(l,r\) 的中点 \(mid\) ，求出其决策点 \(MID\)。那么 $[l,mid - 1] $ 的决策点肯定在 \([L,MID]\) 中，\([mid + 1,r]\) 的决策点肯定在 \([MID,R]\) 中，于是可以进行递归：\(\texttt{solve(l,mid-1,L,MID),solve(mid+1,r,MID,R)}\) 。
时间复杂度为 \(\mathcal{O}(n\log n)\) 。
注：如果把 \(p_i\) 存为实数，然后进行取整，那么决策点就可以看作是唯一的。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n,a[N];
double ans[N];
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 (int i = L + 1;i <= min(mid,R);i++)
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(){
scanf("%d",&n);
for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
solve(1,n,1,n); // 正向求解
for (int i = 1;i <= n / 2;i++){
swap(a[i],a[n - i + 1]);
swap(ans[i],ans[n - i + 1]);
}
solve(1,n,1,n); // 反向求解
for (int i = 1;i <= n / 2;i++){
swap(a[i],a[n - i + 1]);
swap(ans[i],ans[n - i + 1]);
}
for (int i = 1;i <= n;i++) printf("%.0lf\n",ceil(ans[i])); // 上取整输出答案
}