```
#include<bits/stdc++.h>
using namespace std;
#define val(j,i) a[j]+sq[i-j]
int read(){
int ss=0,ww=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
ww=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ss=ss*10+ch-'0';
ch=getchar();
}
return ss*ww;
}
const int N=500010;
int a[N],n;
double f[N],sq[N];
struct dat{
int j;
int l;
int r;
}q[N];
int head,tail;
void insert(int i){
int pos=n+1;
while(head<=tail&&val(q[tail].j,q[tail].l)<=val(i,q[tail].l)){
pos=q[tail].l;
tail--;
}
if(head>tail){
tail++;
q[tail].l=i;
q[tail].r=n;
q[tail].j=i;
return;
}
if(val(i,q[tail].r)>=val(q[tail].j,q[tail].r)){
int l=q[tail].l;
int r=q[tail].r;
while(l<r){
int mid=(l+r)/2;
if(val(i,mid)>=val(q[tail].j,mid))
r=mid;
else
l=mid+1;
}
pos=r;
q[tail].r=r-1;
}
if(pos!=n+1){
tail++;
q[tail].j=i;
q[tail].l=pos;
q[tail].r=n;
}
}
void solve(){
head=1;
tail=0;
for(int i=1;i<=n;i++){
insert(i);
if(q[head].r<i)
head++;
q[head].l=i;
f[i]=max(f[i],val(q[head].j,i));
}
}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i++)
sq[i]=sqrt(i);
solve();
for(int i=1;i<=n/2;i++){
swap(f[i],f[n-i+1]);
swap(a[i],a[n-i+1]);
}
solve();
for(int i=n;i>=1;i--)
printf("%d\n",max((int)(ceil(f[i]))-a[i],0));
return 0;
}
```
by MeowScore @ 2022-04-22 18:06:10
呃，标题打错了，是“四边形不等式”
by MeowScore @ 2022-04-22 18:06:55
@[Liu_Kevin](/user/140360) %%%蒟蒻dp还没学好
by DeepWinter @ 2022-04-22 18:17:28
@[Liu_Kevin](/user/140360) 您好，久仰大名。
```cpp
while(head<=tail&&val(q[tail].j,q[tail].l)<=val(i,q[tail].l)){
pos=q[tail].l;
tail--;
}
if(head>tail){
tail++;
q[tail].l=i;
q[tail].r=n;
q[tail].j=i;
return;
}
```
改成
```c
while(head<tail&&val(q[tail].j,q[tail].l)<=val(i,q[tail].l)){
pos=q[tail].l;
tail--;
}
```
栈首元素不保证 r >= i
by CodingJellyfish @ 2022-04-22 20:41:40
@[DoctorJellyfish](/user/52381)
神仙太巨了 Orz
您 tql
I am a noob
by MeowScore @ 2022-04-22 22:04:24