codeforces #333 div 2 D. Lipshitz Sequence

2015年12月23日 0 作者 CrazyKK

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

具体的证明见这里:

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

  • Aj > Ai, Ak — we can see that L1(i, j) > L1(i, k), since |Aj - Ai| = Aj - Ai > Ak - Ai = |Ak - Ai| and j - i < k - i; we just need to divide those inequalities
  • Aj < Ai, Ak — this is similar to the previous case, we can prove that L1(j, k) > L1(i, k) in the same way
  • Ai ≤ Aj ≤ Ak — this case requires more work:
    • we’ll denote d1y = Aj - Ai, d2y = Ak - Aj, d1x = j - i, d2x = k - j
    • then, L1(i, j) = d1y / d1x, L1(j, k) = d2y / d2x, L1(i, k) = (d1y + d2y) / (d1x + d2x)
    • let’s prove it by contradiction: assume that L1(i, j), L1(j, k) < L1(i, k)
    • d1y + d2y = L1(i, j)d1x + L1(j, k)d2x < L1(i, k)d1x + L1(i, k)d2x = L1(i, k)(d1x + d2x) = d1y + d2y, which is a contradiction

We’ve just proved that to any L1 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 L1; a sufficient amount of such operations will give us k = i + 1. Therefore, the max. L1can 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代表能到达的右边和左边的最远位置。