【BZOJ】2216: [Poi2011]Lightning Conductor

题意

给一个长度为(n)的序列(a_i)，对于每个(1 le i le n)，找到最小的非负整数(p)满足 对于任意的(j), (a_j le a_i + p - sqrt{|i-j|})

分析

我们正反dp一下。

题解

令(d(i))表示最小的(p)，则(d(i) = max(a_j+sqrt{i-j})-a_i, j < i)。
其实发现这是有决策单调性的。即对于决策(j)和(k(j > k))，如果(j)在(i)时比(k)在(i)优了，则对于所有(x > i)，决策(j)都比决策(k)优。所以我们用一个栈来维护一下最优区间即可，更新区间用二分，复杂度(O(nlogn))。

#include <bits/stdc++.h>
using namespace std;
typedef double lf;
inline int getint() {
	int x=0, c=getchar();
	for(; c<48||c>57; c=getchar());
	for(; c>47&&c<58; x=x*10+c-48, c=getchar());
	return x;
}
const int N=500005;
struct ip {
	int id, l, r;
}q[N];
int n, a[N];
inline lf cal(int j, int i) {
	return a[j]-a[i]+sqrt(i-j);
}
void dp(lf *f) {
	ip *fr=q, *ta=q;
	*ta++=(ip){1, 2, n};
	for(int i=2; i<=n; ++i) {
		for(; fr+1!=ta && (fr+1)->l<=i; ++fr);
		f[i]=cal(fr->id, i);
		++fr->l;
		for(; fr!=ta && fr->l>fr->r; ++fr);
		for(; fr!=ta && cal((ta-1)->id, (ta-1)->l)<cal(i, (ta-1)->l); --ta);
		if(fr!=ta) {
			ip *b=ta-1;
			int l=b->l, r=b->r;
			while(l<=r) {
				int mid=(l+r)>>1;
				if(cal(b->id, mid)<cal(i, mid)) {
					r=mid-1;
				}
				else {
					l=mid+1;
				}
			}
			++r;
			if(r<=n) {
				b->r=r-1;
				*ta++=(ip){i, r, n};
			}
		}
		else {
			*ta++=(ip){i, i+1, n};
		}
	}
}
lf f[N], g[N];
int main() {
	n=getint();
	for(int i=1; i<=n; ++i) {
		a[i]=getint();
	}
	dp(f);
	reverse(a+1, a+1+n);
	dp(g);
	for(int i=1; i<=n; ++i) {
		printf("%d
", max(0, int(ceil(max(f[i], g[n-i+1])))));
	}
	return 0;
}