P3515 [POI2011]Lightning Conductor

题意:给出一个序列，对于$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; } ```