P3515 [POI 2011] Lightning Conductor

考虑正着做一遍，反着做一遍，绝对值就被拆开了。下面只讨论正着做。
\(f(x)=\sqrt{x+1}-\sqrt x\) 是单调递减的，所以对于 \(j_1<j_2\)，一定能找到一个 \(w\) 使得对于任意 \(i\ge w\)，都有 \(h_{j_2}+\sqrt{i-j_2}\ge h_{j_1}+\sqrt{i-j_1}\)，所以有决策单调性，用单调队列维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=500010;
int n,h[maxn],f[maxn],g[maxn];
deque<int>vt;
double js(int i,int j){
    return h[j]+sqrt(abs(j-i));
}
int find(int i,int j,int ll,int rr){
    int l=ll,r=rr,ans=rr;
    while(l<=r){
        int mid=l+r>>1;
        if(js(mid,i)<=js(mid,j)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int find2(int i,int j,int ll,int rr){
    int l=ll,r=rr,ans=ll;
    while(l<=r){
        int mid=l+r>>1;
        if(js(mid,i)<=js(mid,j)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
signed main(){
    read(n);for(int i=1;i<=n;i++) read(h[i]);
    for(int i=1;i<=n;i++){
        while(vt.size()>1&&find(vt.back(),i,i,maxn)<=find(vt[vt.size()-2],vt.back(),i,maxn)) vt.pop_back();
        vt.push_back(i);
        while(vt.size()>1&&js(i,vt[1])>=js(i,vt[0])) vt.pop_front();
        f[i]=(int)ceil(js(i,vt[0]))-h[i];
    }
    vt.clear();
    for(int i=n;i>=1;i--){
        while(vt.size()>1&&find2(vt.back(),i,0,i)>=find2(vt[vt.size()-2],vt.back(),0,vt[vt.size()-2])) vt.pop_back();
        vt.push_back(i);
        while(vt.size()>1&&js(i,vt[1])>=js(i,vt[0])) vt.pop_front();
        g[i]=(int)ceil(js(i,vt[0]))-h[i];
    }
    for(int i=1;i<=n;i++,write("\n")) write(max(f[i],g[i]));
    return 0;
}