洛谷 P3515 [ POI 2011 ] Lightning Conductor —— 决策单调性DP

#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; q[++t]=N(i,ret+1,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\n",ans[i]);
    return 0;
}