[bzoj4850][Jsoi2016]灯塔【暴力】

【题目链接】
　　https://www.lydsy.com/JudgeOnline/problem.php?id=4850
【题解】
　　考虑从位置i到位置i+1只有O(N−−√)$O(\sqrt{N})$个灯塔距离该位置的相对距离发生了改变。暴力修改即可。
　　具体实现时，从左往右做一遍处理出左边的影响，再从右往左做一遍处理右边的影响。由于距离不会变小，所以不用删去原来的距离所造成的影响。
　　时间复杂度O(NN−−√)$O(N\sqrt{N})$
　　

/* --------------
    user Vanisher
    problem bzoj-4850 
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    N       100010
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
int ans[N],h[N],now[N],n;
int main(){
    n=read();
    for (int i=1; i<=n; i++) h[i]=read();
    for (int i=1; i<=n; i++){
        for (int j=1, k=1; i-j>0; j=j+k, k=k+2)
            now[k/2+1]=max(now[k/2+1],h[i-j]);
        for (int j=1, k=1; j<=n; j=j+k, k=k+2)
            ans[i]=max(ans[i],now[k/2+1]+k/2+1);
    } 
    memset(now,0,sizeof(now));
    for (int i=n; i>=1; i--){
        for (int j=1, k=1; i+j<=n; j=j+k, k=k+2)
            now[k/2+1]=max(now[k/2+1],h[i+j]);
        for (int j=1, k=1; j<=n; j=j+k, k=k+2)
            ans[i]=max(ans[i],now[k/2+1]+k/2+1);
    } 
    for (int i=1; i<=n; i++)
        printf("%d
",max(ans[i]-h[i],0));
    return 0;
}