Description

Solution

据说这是板子题……

题目让求最小的(p_i)满足(p_ige a_j + sqrt{|j-i|} - a_i)，也即(p_i=max_{j=1}^n(a_j+sqrt{|j-i|})-a_i)。绝对值比较难以处理，所以把绝对值拆开:

[p_i = max(max_{j=1}^i { a_j+sqrt{i-j}}, max_{j=i+1}^n {a_j+sqrt{j-i}}) - a_i ]

显然前后可以分开算。只看前面。

我们把(a_j+sqrt{i-j})看作一个关于(i)函数，显然，这个函数是单调的。我们就只需要维护当前的所有函数，然后取在(i)处的最大值就行了。当然是要用单调队列的，维护相邻两个函数的交点，然后就可以轻松的判断(i)要从哪个位置转移。

总的来说，我们要维护一些函数，它们未来能够成为所有函数的最大值，这可以用单调队列维护。