给出 \(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]\)），答案还更优。
我们还需要发现一个性质，那就是如果现在有两个区间 \([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\) 中。
根据这样两个性质，我们可以得到很多个区间。不难发现这些区间是独立的。最后我们取前 \(k\) 大的区间即可。
具体代码可以戳这里。
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();
}