题意
给定一个长度为 $n$ 的数组 $a$，要求选出若干区间，每段区间长度不超过 $k$，求被选出的数的和的最大值。
$n = 10^6, 0 \leq a_i \leq 10^9$
题解
脑抽了，一下没想出来。
设 $f_i$ 表示 只看数组中 $1$ 到 $i$ 的答案，且要求 $a_i$ 必须选。
$f_i$ 可以由前面的一段转移过来。
加上单调队列或者线段树优化即可。
代码
tp op1(tp x, tp y) { return max(x, y); }
tp op2(tp x, tp y) { return x + y; }
tp e() { return 0; }
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, k; bin >> n >> k;
if (!k) { bin << "0\n"; return; }
lib::Segtree<tp, op1, e, tp, op2, op2, e> f(n + 2);
lib::Light_Segtree<tp, op2, e> a(n + 1);
for (tp i = 1; i <= n; ++i) {
tp x; bin >> x;
a.set(i, x);
}
for (tp i = 1; i <= n + 1; ++i) {
f.apply(max(ZERO, i - k - 1), i - 2, a.get(i - 1));
f.set(i, f.product(max(ZERO, i - k - 1), i - 2));
// for (tp j = max(ONE, i - k); j < i; ++j) {
// f.set(i, max(f.get(i), f.get(j - 1) + a.product(j, i - 1)));
// }
}
bin << f.all_product() << '\n';
}