P3515 [POI2011]Lightning Conductor

2018-10-09 23:37:47


题意:给出一个序列,对于 $i∈[1,n]$ ,求最小的非负整数 $p_i$ ,使得对于任意的 $j∈[1,n]$ ,都有 $a_j<=a_i+p_i-sqrt(|i-j|)$


移项,得 $p_i>=a_j-a_i+sqrt(|i-j|)$

所以 $p_i=max\left\{a_j+sqrt(|i-j|)\right\}-a_i$

去掉绝对值,得 $p_i=max\left\{max\left\{a_j+sqrt(i-j),j∈[1,i-1]\right\},max\left\{a_j+sqrt(j-i),j∈[i+1,n]\right\}\right\}-a_i$

后一种情况只需要前一种情况把序列反转一下就好了

只讨论 $j<i$ 时的做法

这明显是一个可以决策单调性优化的式子

对于每个 $j$ ,把 $a_j+sqrt(i-j)$ 看成一个关于 $i$ 的函数 $f_j$

因为 $sqrt$ 的增速是递减的

所以有可能会有较大的 $j$ 在某个位置函数值超过较小的 $j$

用单调队列按 $j$ 从小到大来维护这些函数

两个相邻的函数会有一个交点 $k_{j,j+1}$

需要满足 $k$ 是严格递增的

如果 $k_{j,j+1}>=k_{j+1,j+2}$ ,

那么 $f_{j+1}$ 其实是没有用到的

从 $1$ 到 $n$ 枚举 $i$ ,考虑怎样把 $f_i$ 加入队列

设队尾的决策为 $t$ ,当 $k_{t-1,t}>=k_{t,i}$ 时,有 $f_t(k_{t-1,t})<=f_i(k_{t-1,t})$ , $t$ 就没有用了,出队

然后把 $i$ 加入队列

检查一下队首,如果 $k_{h,h+1}<=i$ ,那么 $h$ 也没用了,出队

这样队首就是所有函数中的最大值

最后把序列反转再做一遍就ok了

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define reg register
using namespace std;
const int N=5e5+5;
const double eps=1e-8;
int n,a[N],p[N],q[N];
double b[N],f[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline double calc(int x,int y){return a[y]+b[x-y];}
inline int getpos(int x,int y)
{
    int l=y,r=p[x]?p[x]:n,pos=r+1;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (calc(mid,x)-calc(mid,y)<=eps) pos=mid,r=mid-1;
        else l=mid+1;
    }
    return pos;
}
inline void work()
{
    for (reg int i=1,head=1,tail=0;i<=n;i++)
    {
        while (head<tail&&calc(p[tail-1],q[tail])<calc(p[tail-1],i)) --tail;
        p[tail]=getpos(q[tail],i); q[++tail]=i;
        while (head<tail&&p[head]<=i) ++head;
        f[i]=max(f[i],calc(i,q[head]));
    }
}
int main()
{
    n=read();
    for (reg int i=1;i<=n;i++) a[i]=read(),b[i]=sqrt(i);
    work(); reverse(a+1,a+n+1); reverse(f+1,f+n+1);
    memset(p,0,sizeof(p)); work();
    for (reg int i=n;i;i--) printf("%d\n",max((int)ceil(f[i])-a[i],0));
    return 0;
}