[POI2011]Lightning Conductor

题目

啊，不难发现我们要做的就是对于每一个\(i\)找到一个\(j\)使得\(a_j+\sqrt{|i-j|}\)最大

不失一般性的只讨论\(j<i\)的情况，对于\(j>i\)的情况我们完全可以将序列翻转再来一遍

不难发现存在决策单调性，因为\(f(x)=\sqrt{x}\)的导数是\(f'(x)=\frac{1}{\sqrt{2x}}\)，这个导数是递减的，也就是说\(f(x)\)的增长原来越慢；所以对于两个决策点\(j<k\)，一旦\(k\)优于\(j\)了，那么更靠后的位置\(k\)也会优于\(j\)

于是我们维护一个决策点的单调队列，设\(f(j,k)\)表示\(k\)决策最早优于\(j\)决策的时间，显然\(f(j,k)\)可以二分求出；每次插入的时候发现队尾没啥用了就弹出；取答案的时候看看队首是不是最优的，不优的话就弹

代码

#include<bits/stdc++.h>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=5e5+5;
int q[maxn],h,t;
int a[maxn],n,ans[maxn];
inline double calc(int j,int i) {return a[j]+sqrt(i-j);}
inline int f(int x,int y) {
    int l=y,r=n,nw=n+1;
    while(l<=r) {
        int mid=l+r>>1;
        if(calc(x,mid)<=calc(y,mid)) nw=mid,r=mid-1;else l=mid+1;
    }
    return nw;
}
int main() {
    scanf("%d",&n);for(re int i=1;i<=n;i++)scanf("%d",&a[i]);h=1,t=0;
    for(re int i=1;i<=n;i++) {
        while(h<t&&f(q[t-1],q[t])>=f(q[t],i)) t--;
        q[++t]=i;
        while(h<t&&f(q[h],q[h+1])<=i) ++h;
        double k=calc(q[h],i);
        ans[i]=ceil(k);
    }
    h=1,t=0;std::reverse(a+1,a+n+1);
    for(re int i=1;i<=n;i++) {
        while(h<t&&f(q[t-1],q[t])>=f(q[t],i)) t--;
        q[++t]=i;
        while(h<t&&f(q[h],q[h+1])<=i) ++h;
        double k=calc(q[h],i);
        ans[n-i+1]=max(ceil(k),ans[n-i+1]);
    }
    std::reverse(a+1,a+n+1);
    for(re int i=1;i<=n;i++) printf("%d\n",ans[i]-a[i]);return 0;
}