[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
",ans[i]-a[i]);return 0;
}