## codeforces 455 E. Function (斜率优化，线段树套凸包)

f[i][j] = min (f[i-1][j],f[i-1][j-1])

Function is calculated as follows: , ki — how many times we visited the i th element of the array a.

sum[y] - sum[l] + a[l]·(x - (y - l))

sum[y] - sum[l] + a[l]·(x - (y - l)) = sum[y] - sum[l] + a[l]·(x - y + l) = sum[y] - sum[l] + a[l]·l + a[l]·(x - y) = sum[y] + (a[l]·(x - y) + a[l]·l - sum[l])

You may notice that in brackets something like the equation of the line — K·X + B. That’s very similar to the equation of the line:a[l]·(x - y) + a[ll - sum[l], where K = a[l], X = (x - y), B = a[ll - sum[l].

Now we must find minimum for all l and fixed X = (x - y).

We have n lines, i. e. for every element in array a one line (Ki, Bi).

, where (Ki, Bi)i-th line. Ki = a[i], Bi = a[ii - sum[i].

For fast answer calculation we must use Convex Hull Trick with segment tree. In every vertex of segment tree we keep all lines for segment of this vertex. This requires space, because each line lies in vertices. And we can answer query in operations. Because we visit vertices and each vertex need in operations. You can learn the theory about Convex

Remainder: convex hull trick lets us maintain k linear functions of the form fi(x) = aix + bi and answer efficiently (in time proportional to number of functions) to the queries Q(x) = min1 ≤ i ≤ k fi(x) (given x).

Now we will be able to solve the problem if we can answer a bit more general kind of queries: we consider only lines with indices from given L and R; formally, Q(x, L, R) = minL ≤ i ≤ R fi(x).

How can we do it? Let’s make a segment tree! Let’s say we have such m that 2m ≥ n. Then the root contains the convex hull of lines having indices [0, 2m - 1], its left child contains [0, 2m - 1 - 1], right child [2m - 1, 2m - 1]and so on. We can costruct all these hulls one by one; without any optimizations it gives us time .

Now let’s say we have to answer the query Q(x, L, R). Then we just “break” the interval [L, R] into base intervals (in the same way a segment tree does) and for each of such base intervals we find its minimum at x. Now we see that the answer is the smallest of these minima. It doesn’t matter that we consider some groups of lines from interval [L, R] separately — still, we can just take the smallest of the results.

What’s the time? We have base intervals, for each of them we can compute the answer in , so total time is . There are some ways which let us compute all answers off-line in , but it’s not the subject 😛

wjmzbmr关于斜率优化的讲解