2216: [Poi2011]Lightning Conductor

2216: [Poi2011]Lightning Conductor

Time Limit: 25 Sec   Memory Limit: 64 MB
Submit: 935   Solved: 318
[ Submit][ Status][ Discuss]

Description

已知一个长度为n的序列a1,a2,...,an。
对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p - sqrt(abs(i-j))

Input

第一行n，(1<=n<=500000)
下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)

Output

n行，第i行表示对于i，得到的p

Sample Input

6
5
3
2
4
2
4

Sample Output

2
3
5
3
5
4

HINT

Source

[ Submit][ Status][ Discuss]



一开始想，把原式改写一下，变成aj + sqrt(abs(i - j)) <= ai + p

对于每个i，左边的所有数和右边的所有数都查询左式的max，然后处理p

因为p是非负整数，不妨将sqrt上取整，这样不同的sqrt只有根号种

左右两边各分根号段，RMQ查询，复杂度O(nsqrt(n))，结果无情TLE。。。

正解是决策单调性，，果然自己是做不出啊。。。

就只讨论j在i左边的情形，j在i右边反过来再做一遍就是了

假设有三个位置，j < k < i，如果aj + sqrt(i - j) < ak + sqrt(i - k)，那么位置j永远都没用了

因为y = x^(0.5)这个函数的斜率是单调递减的，也就是说越往后增长越慢

既然如此，每个点能作为最优决策的区间一定是连续的一段，或根本不存在

因为当在某个位置，这个点作为决策劣于后面的某个点后，就不再考虑了

这样，维护一个双端队列，队列中的元素都是三元组(id,l,r)的形式，

代表当前的情形下，编号为id的点在区间[l,r]都是作为最优决策的

从左往右递推i，插入i

对于i来说，最优决策就是队列头的那个元素了

然后从队列尾开始，如果一整段内全部劣于i，都替换掉

可能对于某个元素(p,l,r)，满足p -> r < i -> r 但是p -> l > i ->l

说明在[l,r]内必定存在一点k能作为分界点，二分出这个k就行

边界调了快1h。。。GG

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn = 5E5 + 50;
typedef double DB;

struct data{
	int id,l,r; data(){}
	data(int id,int l,int r): id(id),l(l),r(r){}
}Q[maxn];

int n,head,tail,A[maxn],f[maxn],g[maxn];

DB Work(int x,int y)
{
	return (DB)(A[x]) + sqrt((DB)abs(y - x));
}

data Calc(data k,int t)
{
	int L = k.l,R = k.r + 1;
	while (R - L > 1)
	{
		int mid = (L + R) >> 1;
		if (Work(k.id,mid) <= Work(t,mid)) R = mid;
		else L = mid;
	}
	data ret = data(t,0,n);
	ret.l = Work(k.id,L) < Work(t,L) ? L : R;
	return ret;
}

bool Judge(data k,int t)
{
	return Work(k.id,k.l) < Work(t,k.l);
}

void Solve(int *F)
{
	head = 1; tail = 0;
	for (int i = 1; i <= n; i++)
	{
		if (head <= tail && ++Q[head].l > Q[head].r) ++head;
		if (head > tail || Work(i,n) > Work(Q[tail].id,n))
		{
			while (head <= tail && Judge(Q[tail],i)) --tail;
			if (head > tail) Q[++tail] = data(i,i,n);
			else
			{
				data ret = Calc(Q[tail],i);
				Q[tail].r = ret.l - 1; Q[++tail] = ret;
			}
		}
		F[i] = ceil(Work(Q[head].id,i));
	}
}

int getint()
{
	char ch = getchar(); int ret = 0;
	while (ch < '0' || '9' < ch) ch = getchar();
	while ('0' <= ch && ch <= '9')
		ret = ret*10 + ch - '0',ch = getchar();
	return ret;
}

int main()
{
	#ifdef DMC
		freopen("DMC.txt","r",stdin);
	#endif
	
	n = getint();
	for (int i = 1; i <= n; i++) 
		A[i] = getint(); Solve(f);
	reverse(A + 1,A + n + 1); Solve(g);
	reverse(A + 1,A + n + 1); reverse(g + 1,g + n + 1);
	for (int i = 1; i <= n; i++)
		printf("%d\n",max(max(f[i],g[i]) - A[i],0));
	return 0;
}