codeforces #333 div 2 D. Lipshitz Sequence

http://codeforces.com/contest/602/problem/D
题意：见题目描述。
思路：我们很容易发现，l[h]函数其实就是在求区间斜率的最大值。哦不对，是斜率的绝对值的最大值。而且一个显而易见的结论是，斜率最大值一定是由相邻的点得到。画图可以很容易看出。

具体的证明见这里：

In order to prove it properly, we’ll consider three numbers A_i, A_j, A_k (i < j < k) and show that one of the numbers L₁(i, j),L₁(j, k) is  ≥ L₁(i, k). W.l.o.g., we may assume A_i ≤ A_k. There are 3 cases depending on the position of A_j relative to A_i, A_k:

• A_j > A_i, A_k — we can see that L₁(i, j) > L₁(i, k), since |A_j - A_i| = A_j - A_i > A_k - A_i = |A_k - A_i| and j - i < k - i; we just need to divide those inequalities
• A_j < A_i, A_k — this is similar to the previous case, we can prove that L₁(j, k) > L₁(i, k) in the same way
• A_i ≤ A_j ≤ A_k — this case requires more work:
  • we’ll denote d_1y = A_j - A_i, d_2y = A_k - A_j, d_1x = j - i, d_2x = k - j
  • then, L₁(i, j) = d_1y / d_1x, L₁(j, k) = d_2y / d_2x, L₁(i, k) = (d_1y + d_2y) / (d_1x + d_2x)
  • let’s prove it by contradiction: assume that L₁(i, j), L₁(j, k) < L₁(i, k)
  • d_1y + d_2y = L₁(i, j)d_1x + L₁(j, k)d_2x < L₁(i, k)d_1x + L₁(i, k)d_2x = L₁(i, k)(d_1x + d_2x) = d_1y + d_2y, which is a contradiction

We’ve just proved that to any L₁ computed for two elements A[i], A[k] with k > i + 1, we can replace one of i, j by a point jbetween them without decreasing L₁; a sufficient amount of such operations will give us k = i + 1. Therefore, the max. L₁can be found by only considering differences between adjacent points.

这样子就好做了很多。由于斜率绝对值的最大值一定在由相邻的两个点得到。而相邻两个点的横坐标差1，所以斜率的绝对值就变成了相邻元素差的最大值。因此我们可以预处理一个数组b，表示相邻元素的差的绝对值。

接下来的问题就变成了如何求b的一段区间里的所有子区间的最大值的和。我们的思路是考虑这个区间里每个元素对答案的贡献。显然，对于b中越大的元素，它对答案的贡献会越多，因为会有更多包含它的区间以它为最大值。具体来讲，对于这个区间的每一个元素，我们可以分别向左和右边扩展，看最大能到哪里。

比如3 4 3 8 2 7 1，对于8，左边可以到达3，与8的距离为3，右边可以到达1，与8的距离为3，那么8对答案的贡献为(3+1)*(3+1)*8，也就是说一共有4*4个区间的最大值为8.对于7，左边可以到2，距离7为1，右边可以到1，距离7长度为1，那么7对答案的贡献就是（1+1）×（1+1）*7，也就是有4个区间的最大值为7.分别为{2}，{2,7}，{7,1}，{2,7,1}

由于q不算很大，可以直接搞…用两个数组right和left代表能到达的右边和左边的最远位置。