LibreOJ 2157 「POI2011」Lightning Conductor

由于本人比较弱，所以本题没有太严谨的证明……
添加了（本来懒得写的）四边形不等式证明。

首先显然地，pi=⌈max1≤j≤n(aj+√|i−j|)⌉−ai。
这个绝对值看着很不爽，我们考虑正着做一遍然后再倒着做一遍。
那么问题变成求 fi=max1≤j≤i(aj+√i−j)。

朴素显然是 O(n2) 的，然鹅我们发现一点：当 j 一定时，关于 i 的函数 √i−j 的增长是越来越慢的，即 (√i−j)″≤0。
所以这题是具有决策单调性的。
（可以把每个决策对应的函数图像画出来）

具体证明（并不严谨）：
记 w(j,i)=√i−j，则只需证明 ∀a<b 有 w(a,b+1)+w(a+1,b)≤w(a,b)+w(a+1,b+1)

即 √b−a+1+√b−a−1≤2√b−a

考虑换元，令 c=b−a，则有 √c+1+√c−1≤2√c

移项有 √c+1−√c≤√c−√c−1

则可考虑证明 f(x)=√x+1−√x 在 (0,∞) 上单调不增。
即 f′(x)=12(1√x+1−1√x)≤0。
12(1√x+1−1√x)≤01√x+1−1√x≤0√x−√x+1√x√x+1≤0∵√x≥0,√x+1≥0∴√x−√x+1≤0√x+1≥√x

这就很显然成立了（

考虑用单调队列去维护最优决策，然后套路地决策单调性 DP 即可。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 5e5;
int n,a[N + 5];
double rt[N + 5],f[N + 5];
inline double calc(int x,int y)
{
    return a[x] + rt[y - x];
}
struct note
{
    int x,l,r;
} q[N + 5];
int head,tail;
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),rt[i] = sqrt(i);
    q[head = tail = 1] = (note){1,2,n},f[1] = calc(1,1);
    for(register int i = 2;i <= n;++i)
    {
        for(;head < tail && q[head].r < i;++head);
        f[i] = calc(q[head].x,i);
        if(calc(q[tail].x,q[tail].r) <= calc(i,q[tail].r))
        {
            for(;head < tail && calc(q[tail].x,q[tail].l) <= calc(i,q[tail].l);--tail);
            int now,l = q[tail].l,r = n,mid;
            while(l <= r)
            {
                mid = l + r >> 1;
                if(calc(q[tail].x,mid) <= calc(i,mid))
                    r = mid - 1,now = mid;
                else
                    l = mid + 1;
            }
            q[tail].r = now - 1,q[++tail] = (note){i,now + 1,n};
        }
    }
    reverse(a + 1,a + n + 1),reverse(f + 1,f + n + 1);
    q[head = tail = 1] = (note){1,2,n},f[1] = max(f[1],calc(1,1));
    for(register int i = 2;i <= n;++i)
    {
        for(;head < tail && q[head].r < i;++head);
        f[i] = max(f[i],calc(q[head].x,i));
        if(calc(q[tail].x,q[tail].r) <= calc(i,q[tail].r))
        {
            for(;head < tail && calc(q[tail].x,q[tail].l) <= calc(i,q[tail].l);--tail);
            int now,l = q[tail].l,r = n,mid;
            while(l <= r)
            {
                mid = l + r >> 1;
                if(calc(q[tail].x,mid) <= calc(i,mid))
                    r = mid - 1,now = mid;
                else
                    l = mid + 1;
            }
            q[tail].r = now - 1,q[++tail] = (note){i,now + 1,n};
        }
    }
    for(register int i = n;i;--i)
        printf("%d\n",(int)ceil(max(f[i],calc(i,i))) - a[i]);
}