题意
给一个长度为\(n\)的序列\(a_i\)，对于每个\(1 \le i \le n\)，找到最小的非负整数\(p\)满足 对于任意的\(j\), \(a_j \le a_i + p - \sqrt{|i-j|}\)
分析
我们正反dp一下。
题解
令\(d(i)\)表示最小的\(p\)，则\(d(i) = max(a_j+\sqrt{i-j})-a_i, j < i\)。
其实发现这是有决策单调性的。即对于决策\(j\)和\(k(j > k)\)，如果\(j\)在\(i\)时比\(k\)在\(i\)优了，则对于所有\(x > i\)，决策\(j\)都比决策\(k\)优。所以我们用一个栈来维护一下最优区间即可，更新区间用二分，复杂度\(O(nlogn)\)。
#include <bits/stdc++.h>
using namespace std;
typedef double lf;
inline int getint() {
int x=0, c=getchar();
for(; c<48||c>57; c=getchar());
for(; c>47&&c<58; x=x*10+c-48, c=getchar());
return x;
}
const int N=500005;
struct ip {
int id, l, r;
}q[N];
int n, a[N];
inline lf cal(int j, int i) {
return a[j]-a[i]+sqrt(i-j);
}
void dp(lf *f) {
ip *fr=q, *ta=q;
*ta++=(ip){1, 2, n};
for(int i=2; i<=n; ++i) {
for(; fr+1!=ta && (fr+1)->l<=i; ++fr);
f[i]=cal(fr->id, i);
++fr->l;
for(; fr!=ta && fr->l>fr->r; ++fr);
for(; fr!=ta && cal((ta-1)->id, (ta-1)->l)<cal(i, (ta-1)->l); --ta);
if(fr!=ta) {
ip *b=ta-1;
int l=b->l, r=b->r;
while(l<=r) {
int mid=(l+r)>>1;
if(cal(b->id, mid)<cal(i, mid)) {
r=mid-1;
}
else {
l=mid+1;
}
}
++r;
if(r<=n) {
b->r=r-1;
*ta++=(ip){i, r, n};
}
}
else {
*ta++=(ip){i, i+1, n};
}
}
}
lf f[N], g[N];
int main() {
n=getint();
for(int i=1; i<=n; ++i) {
a[i]=getint();
}
dp(f);
reverse(a+1, a+1+n);
dp(g);
for(int i=1; i<=n; ++i) {
printf("%d\n", max(0, int(ceil(max(f[i], g[n-i+1])))));
}
return 0;
}