夏晓光(loveJY)的博客

唉...二分是又一个细节吧.....

$a_j+\sqrt{|i-j|}<=a_i+p$

拿到题我们就应该想到找每个数上述式子最大的j

观察后面根号函数,你会发现他的导函数单调递减!有决策单调性了

而与此同时我们要求的是最大值,所以可以用单调队列来优化

就是单调队列优化决策单调性的板子.....

直接上就好了,正着做一遍反着来一遍

然后最后处理答案随便搞一下就好

但是nmd卡细节

记得我们决策单调性有一个二分的步骤吗?

里面我们的l,r一定要限制好范围!!!!

对于r,如果k[r]存在(即有右端点的限制)我们就设置右端点为r

对于l,我们输入了x,y两个决策点想要找一个不错的,所以我们左端点应该在y之后!

$l=y,r=k_y?k_y+1:n+1$

但是这样诗人小G又不能过,($k_y$一看就很扯吗...),所以我暴力改改参数得到了普适应的一组参数

$l=y,r=n+1$

以后就用这组

二分用$l<r$锁定答案形式

code:

#include<bits/stdc++.h>
using namespace std;
#define db double
const int MAXN = 5e5 + 7;
int n, a[MAXN], que[MAXN], k[MAXN];
db sq[MAXN], f[MAXN];

inline db calc(int x, int y) {
	return a[y] + sq[x - y];
}

inline int bound(int x, int y) {
	int l = y, r = k[y] ? k[y] + 1 : n + 1, mid;
	while(l < r) {
		mid = (l + r) >> 1;
		calc(mid, x) > calc(mid, y) ? l = mid + 1 : r = mid;
	}
	return r;
}	 

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for(int i = 0; i <= n; ++i)
		sq[i] = sqrt(i);
	int h = 1, t = 0;
	for(int i = 1; i <= n; ++i) {
		while(h < t && k[h] <= i)++h;//管束右端点太窄
		// printf("calc in ->%d by%d\n", i, que[h]);
		f[i] = calc(i, que[h]);
		// printf("we get :%lf?\n", f[i]);
		while(h < t && k[t - 1] >= bound(que[t], i))
			--t;
		k[t] = bound(que[t], i);
		// printf("she controlled :%d?\n", k[t]);
		que[++t] = i;
	}
	reverse(a + 1, a + n + 1);
	reverse(f + 1, f + n + 1);
	h = 1, t = 0;
	memset(k, 0, sizeof(k));
	for(int i = 1; i <= n; ++i) {
		while(h < t && k[h] <= i)++h;//管束右端点太窄
		// printf("qwq->:%d %d %lf\n", i, que[h], f[n - i + 1]);
		f[i] = max(f[i], calc(i, que[h]));
		// printf("we get :%lf?\n", f[n - i + 1]);
		while(h < t && k[t - 1] >= bound(que[t], i))
			--t;
		k[t] = bound(que[t], i);
		// printf("%d?\n", k[t]);
		que[++t] = i;
	}
	// reverse(a + 1, a + n + 1);
	for(int i = n; i >= 1; --i) {
		// printf("%lf %d\n", f[i], a[i]);
		printf("%d\n", max((int)ceil(f[i] - a[i]), 0));
	}
	return 0;
}