# CodeForces 391F3 Stock Trading

Author: Fanyi Pu

Published: 2020-02-10

Canonical: <https://pufanyi.com/blog/oi-icpc/codeforces/cf391f3>

CodeForces 391F3 Stock Trading 题解。

给出 $n\,(1\le n\le 4000000)$ 天的股票价格，每天可买进或卖出一股，可以同时买进或卖出，也可以不操作，但最终手上只能有一股。问最多 $k$ 次买进和卖出后的最大收益。

我们先来看一个 $\mathcal{O}(n\log n)$ 的做法。首先我们考虑如果是一段连续的递增股票，那我们相当于是一开始买进，最后卖出。如果这样连续的段小于等于 $k$，那么就直接可以返回答案了。如果比 $k$ 大，那么我们就需要做出这样两种选择：要么选择一个上升的区间放弃，要么选择一段下降的区间把两段上升的区间给连起来。这个东西我们可以用一个堆或者 `set` 来维护。

但是我们还有一个 $\mathcal{O}(n)$ 的做法，需要观察一些性质。我们把读入的股票看成是一个个单调不减的区间。当然有些区间可能只有一个数。

我们考虑一些区间可以合并成一个等价的区间，我们考虑将区间从左往后一个个加入。我们再开一个数组 $b$，记录那些不可能跟后面的区间合并的区间。

我们首先可以得到一个结论：在任一时刻对于那些可能与后面合并的区间，其买入时的价格一定是单调递增的。因为如果不是递增的，如下图情况，原来默认的匹配是 $[x_1,x_2]$，$[x_3,x_4]$，现在加入了一个右端点 $x_5$（左端点在哪儿我们并不需要关心），如果 $x_1$ 跟 $x_5$ 配，那显然不如 $x_3$ 跟 $x_5$ 配，因为这样不仅节省了一段区间（$[x_1,x_2]$），答案还更优。

用更低的买入价 x₃ 与新卖出价 x₅ 匹配

横轴表示时间，纵轴表示价格。灰色点线表示原区间 x₁ 到 x₂、x₃ 到 x₄。 x₃ 的价格低于 x₁。玫瑰色虚线表示尝试将 x₁ 与 x₅ 配对， 加粗的蓝色实线表示改用 x₃ 与 x₅ 配对；后者收益更高，且能单独保留原区间 x₁ 到 x₂。

价格

时间

x1

x2

x3

x4

x5

[View diagram in the original article](https://pufanyi.com/blog/oi-icpc/codeforces/cf391f3)

原区间 尝试 $x_1\to x_5$ 改用 $x_3\to x_5$

$x_3<x_1$，所以 $x_5-x_3>x_5-x_1$；$[x_1,x_2]$ 可单独保留。（左右滑动查看完整图示）

我们还需要发现一个性质，那就是如果现在有两个区间 $[l_1,r_1],[l_2,r_2]$，如果有 $l_1<l_2$ 且 $r_1<r_2$，我们可以把它等价成为 $[l_1,r_2],[l_2,r_1]$ 这样两段区间。而 $[l_2,r_1]$ 是不可能再跟后面的匹配了，所以我们可以直接将其扔进 $b$ 中。

原区间的配对关系

点从左至右按时间排列，纵向位置表示价格，满足 l₁ < l₂ < r₁ < r₂。蓝色实线连接 l₁ 与 r₁，青色实线连接 l₂ 与 r₂。

原区间

l1

r1

l2

r2

[View diagram in the original article](https://pufanyi.com/blog/oi-icpc/codeforces/cf391f3)

$(r_1-l_1)+(r_2-l_2)$

\=

交换端点的配对关系

所有点的位置与原图相同。蓝色实线连接 l₁ 与 r₂，可以继续合并；青色虚线连接 l₂ 与 r₁，表示单独存入 b 的收益 r₁ − l₂。

交换端点

l1

r1

l2

r2

[View diagram in the original article](https://pufanyi.com/blog/oi-icpc/codeforces/cf391f3)

$(r_2-l_1)+(r_1-l_2)$

合并后可继续匹配 独立的收益存入 $b$

交换端点不改变总收益；虚线 $[l_2,r_1]$ 表示单独计入 $b$ 的收益 $r_1-l_2$。

根据这样两个性质，我们可以得到很多个区间。不难发现这些区间是独立的。最后我们取前 $k$ 大的区间即可。

具体代码可以[戳这里](https://codeforces.com/contest/391/submission/69274254)。

```cpp
namespace pufanyi {
    const int maxn = 4000005;

    typedef long long LL;

    LL aa[maxn];
    LL bb[maxn];
    LL sl[maxn];
    LL sr[maxn];

    int Main() {
        int n, k;
        read(n), read(k);
        for (int i = 1; i <= n; ++i) {
            read(aa[i]);
        }
        int m = 0, tl = 0, tr = 0;
        for (int i = 1, j = 1; i <= n; i = j + 1, j = i) {
            while (j <= n && aa[j + 1] >= aa[j]) {
                ++j;
            }
            while (tl && aa[i] <= sl[tl]) {
                bb[++m] = sr[tr--] - sl[tl--];
            }
            sl[++tl] = aa[i];
            while (tr && aa[j] >= sr[tr]) {
                bb[++m] = sr[tr--] - sl[tl--];
            }
            sr[++tr] = aa[j];
        }
        while (tl) {
            bb[++m] = sr[tr--] - sl[tl--];
        }
        k = min(k, m);
        nth_element(bb + 1, bb + k, bb + m + 1, greater<LL>());
        LL ans = 0;
        for (int i = 1; i <= k; ++i) {
            if (bb[i] > 0) {
                ans += bb[i];
            }
        }
        writeln(ans);
        return 0;
    }
}

int main() {
    return pufanyi::Main();
}
```