题目：https://www.luogu.org/problemnew/show/P3515
决策单调性...
参考TJ：https://www.cnblogs.com/CQzhangyu/p/7258256.html
注释WA？？？最近似乎总是WA在二分上...
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int const maxn=5e5+5; int n,a[maxn],ans[maxn],h,t; struct N{ double p,l,r; N(int p=0,int l=0,int r=0):p(p),l(l),r(r) {} }q[maxn]; double calc(int i,int j){return a[i]+sqrt(abs(j-i))-a[j];}//i对j的答案 int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1,h=1,t=0;i<=n;i++) { while(h<=t&&q[h].r<i)h++; if(h<=t)q[h].l=i,ans[i]=max(ans[i],(int)ceil(calc(q[h].p,i))); if(h>t||calc(i,n)>calc(q[t].p,n)) { while(h<=t&&calc(i,q[t].l)>calc(q[t].p,q[t].l))t--; if(h<=t) { // int l=q[t].l,r=q[t].r,ret; // while(l<=r) // { // int mid=((l+r)>>1); // if(calc(i,mid)>=calc(q[t].p,mid))ret=mid,r=mid-1; // else l=mid+1; // } // q[t].l=ret-1; q[++t]=N(i,ret,n); int l=q[t].l,r=q[t].r+1; while(l<r) { int mid=((l+r)>>1); if(calc(i,mid)<calc(q[t].p,mid))l=mid+1; else r=mid; } q[t].r=l-1; q[++t]=N(i,l,n); } else q[++t]=N(i,i+1,n); } } for(int i=n,h=1,t=0;i;i--) { while(h<=t&&q[h].l>i)h++; if(h<=t)q[h].r=i,ans[i]=max(ans[i],(int)ceil(calc(q[h].p,i))); if(h>t||calc(i,1)>calc(q[t].p,1))//1 { while(h<=t&&calc(i,q[t].r)>calc(q[t].p,q[t].r))t--; if(h<=t) { // int l=q[t].l,r=q[t].r,ret; // while(l<=r) // { // int mid=((l+r)>>1); // if(calc(i,mid)>calc(q[t].p,mid))ret=mid,r=mid-1; // else l=mid+1; // } // q[t].l=ret+1; q[++t]=N(i,1,ret); int l=q[t].l,r=q[t].r; while(l<r) { int mid=((l+r)>>1); if(calc(i,mid)<calc(q[t].p,mid))r=mid; else l=mid+1; } q[t].l=r; q[++t]=N(i,1,r-1); } else q[++t]=N(i,1,i-1); } } for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }