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

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

题目链接题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5 个数（a[i] ai≤1E4)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。

参考题解：茶姐的回答（下标好像搞错了，领会意思即可

官方题解

以及前置技能点是：斜率优化+线段树

思路：考虑一排数a[1]到a[n]，原问题可以转化成从a[y]走x-1步，每一步原地不动或者向左移动一个格子后的总的代价。

Function is calculated as follows:

, k__i — how many times we visited the i th element of the array a.

这个式子感觉不是很明确。。。。

窝来解释一下。。。l=y-x+1是可能走到的最左边的点。。。。

终点在【L,Y】区间内都是合法的。。。。

然后考虑代价最小的情况。。。

一定是在最小的格子上尽可能多得停留，在其他格子上只停留一次。。。

对于终点为l的情况，走到y要花费y-l步,一共要走x-1步，那么多出来x-1-(y-l)步，这些步停留在最小的点上是最优的，最小的点上之前停留了一次，现在再多停留x-1-(y-l)次，也就是停留了x-(y-l)次。

那么，另一个结论是，区间[l,y]中，当a[l]为最小的时候才是最优的。。。

为什么呢？

假设a[k] (k>l)是最小，那么以a[k]为终点的情况一定比以a[l]为终点的情况优秀（因为多走了【l,k-1】之间的点。。。走这些点比停留在a[k]的代价大）

因此对于l是终点的情况，一定在a[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]·(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[l]·l - sum[l], where K = a[l], X = (x - y), B = a[l]·l - 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 (K__i, B__i).
Answer for query equal to:
, where (K__i, B__i) — i-th line. K__i = a[i], B__i = a[i]·i - 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

关于斜率优化（convex hull trick）的进一步讲解

Remainder: convex hull trick lets us maintain k linear functions of the form f__i(x) = a__ix + b__i and answer efficiently (in time proportional to number of functions) to the queries Q(x) = _min_1 ≤ i ≤ k f__i(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) = min__L ≤ i ≤ R f__i(x).
How can we do it? Let’s make a segment tree! Let’s say we have such m that 2_m_ ≥ n. Then the root contains the convex hull of lines having indices [0, 2_m_ - 1], its left child contains [0, 2_m_ - 1 - 1], right child [2_m_ - 1, 2_m_ - 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 :P

wjmzbmr关于斜率优化的讲解

第一次写线段树套凸包，虽然线段树窝会写，斜率优化的思想我也明白，不过套在一起如何实现还是参考了不少别人的写法。

  1/* ***********************************************
  2Author :111qqz
  3Created Time :Sun 25 Sep 2016 10:50:45 PM CST
  4File Name :code/cf/problem/455E.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,(rt<<1)+1
 22#define rson m+1,r,(rt<<1)+2
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int maxn = 1E5+7;
 34long double intersect(int k, int b, int kk, int bb) {
 35    return (long double)(b - bb) / (kk - k);
 36}
 37
 38struct ConvexHull {
 39    int * k, * b;
 40    int len;
 41    ConvexHull() : k(0), b(0), len(0) {}
 42    void addLine(int kk, int bb) {
 43        if (len == 1 && k[len - 1] == kk) {
 44            bb = max(b[len - 1], bb);
 45            len = 0;
 46        }
 47        if (len <= 1) {
 48            k[len] = kk;
 49            b[len] = bb;
 50            len++;
 51            return;
 52        }
 53        while (len >= 2 && ((k[len - 1] == kk && b[len - 1] > bb) || (kk != k[len - 1] && intersect(k[len - 2], b[len - 2], k[len - 1], b[len - 1]) >= intersect(k[len - 1], b[len - 1], kk, bb)))) len--;
 54        while (len >= 1 && k[len - 1] == kk && b[len - 1] > bb) len--;
 55        if (len >= 1 && k[len - 1] == kk && b[len - 1] <= bb) return;
 56        k[len] = kk;
 57        b[len] = bb;
 58        len++;
 59    }
 60    int get(int idx, int x) {
 61        return k[idx] * x + b[idx];
 62    }
 63    bool f(int idx, int x) {
 64        return get(idx, x) >= get(idx + 1, x);
 65    }
 66    int getMin(int x) {
 67        int l = -1, r = len - 1;
 68        while (r - l > 1) {
 69            int mid = (l + r) >> 1;
 70            if (f(mid, x)) l = mid;
 71            else r = mid;
 72        }
 73        return get(r, x);
 74    }
 75};
 76
 77int n, q, a[maxn], s[maxn];
 78ConvexHull t[maxn * 4];
 79
 80void mergeCHs(ConvexHull & res, ConvexHull & a, ConvexHull & b) {
 81    res.len = 0;
 82    res.k = new int[a.len + b.len];
 83    res.b = new int[a.len + b.len];
 84    int l = 0, r = 0;
 85    while (l + r != a.len + b.len)
 86        if (l == a.len) {
 87            res.addLine(b.k[r], b.b[r]);
 88            r++;
 89        }
 90        else if (r == b.len) {
 91            res.addLine(a.k[l], a.b[l]);
 92            l++;
 93        }
 94        else if (a.k[l] > b.k[r]) {
 95            res.addLine(a.k[l], a.b[l]);
 96            l++;
 97        }
 98        else {
 99            res.addLine(b.k[r], b.b[r]);
100            r++;
101        }
102}
103
104void PushUp( int rt)
105{
106    mergeCHs(t[rt],t[(rt<<1)+1],t[(rt<<1)+2]);
107}
108void build ( int l,int r,int rt)
109{
110    if (l==r)
111    {
112	t[rt].k = new int[1];
113	t[rt].b = new int[1];
114	t[rt].k[0] = a[l];
115	t[rt].b[0] = a[l] * l - s[l];
116	t[rt].len = 1;
117	return;
118    }
119    int m = (l+r)>>1;
120    build(lson);
121    build(rson);
122    PushUp(rt);
123
124}
125int query(int L,int R,int x,int l,int r,int rt)
126{
127    if (L<=l&&r<=R) return t[rt].getMin(x);
128    int m = (l+r)>>1;
129    int ret = inf;
130    if (L<=m) ret = min(ret,query(L,R,x,lson));
131    if (R>=m+1) ret = min(ret,query(L,R,x,rson));
132    return ret;
133}
134int main()
135{
136	#ifndef  ONLINE_JUDGE
137	freopen("code/in.txt","r",stdin);
138  #endif
139
140	scanf("%d",&n);
141	s[0] = 0 ;
142	for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]),s[i] = s[i-1] + a[i];
143	build(1,n,0);
144	int q;
145	scanf("%d",&q);
146	while (q--)
147	{
148	    int x,y;
149	    scanf("%d%d",&x,&y);
150	    printf("%d\n",s[y] + query(y-x+1,y,x-y,1,n,0));
151	}
152
153  #ifndef ONLINE_JUDGE
154  fclose(stdin);
155  #endif
156    return 0;
157}

Related