P6647这题 我用了两个不同的线段树板子，结果一个AC一个WA 0

//
AC
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define pb emplace_back
#define int LL

using namespace std;
//using namespace __gnu_pbds;
using LL = long long;
using PII = pair<int, int>;

const int N = 1e6 + 10;
const LL INF = 1e12;
int n, k, stk[N], tt;
LL a[N], f[N];

struct Segt_Tree{//需要实现区查区改单改 
	struct Node {LL sum, lz; }t[4 * N];
	#define ls(i) (i << 1)
	#define rs(i) (i << 1 | 1)
	
	void push_up(int cur) {t[cur].sum = max(t[ls(cur)].sum, t[rs(cur)].sum); }
	void f(int cur, int l, int r, LL k) {
		t[cur].sum += k;
		t[cur].lz += k;
	}
	void push_down(int cur, int l, int r) {
		int mid = l + r >> 1;
		f(ls(cur), l, mid, t[cur].lz); f(rs(cur), mid + 1, r, t[cur].lz);
		t[cur].lz = 0;
	}
	
	void modify_qj(int cur, int l, int r, int x, int y, LL k) {
		if (x <= l && y >= r) {
			f(cur, l, r, k); return ;
		}
		int mid = l + r >> 1; push_down(cur, l, r);
		if (x <= mid) modify_qj(ls(cur), l, mid, x, y, k);
		if (y > mid ) modify_qj(rs(cur), mid + 1, r, x, y, k);
		push_up(cur);	
	}
	void modify_dd(int cur, int l, int r, int x, LL k) {
		if (l == r) {
			f(cur, l, r, k); return ;
		}	
		int mid = l + r >> 1; push_down(cur, l, r);
		if (x <= mid) modify_dd(ls(cur), l, mid, x, k);
		else modify_dd(rs(cur), mid + 1, r, x, k);
		push_up(cur);
	}
	LL query(int cur, int l, int r, int x, int y) {
		if (x <= l && y >= r) return t[cur].sum;
		int mid = l + r >> 1; LL ans = -1e18; push_down(cur, l, r);
		if (x <= mid) ans = max(ans, query(ls(cur), l, mid, x, y));
		if (y > mid ) ans = max(ans, query(rs(cur), mid + 1, r, x, y));
		return ans; 
	}
} t;

signed main() {
	scanf("%lld%lld", &n, &k);
	for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
	// f[i] = max(f[j] + maxA(j + 1, i))
	// seg -> the max value of (f[j] + maxA(j + 1, i))
	//seg.build(1, 1, n);
	for (int i = 1; i <= n; i ++ ) {
		while (tt && a[stk[tt]] <= a[i]) {
			t.modify_qj(1, 0, n, stk[tt - 1], stk[tt] - 1, a[i] - a[stk[tt]]);
			-- tt;
		}
		stk[ ++ tt] = i;
		t.modify_qj(1, 0, n, i - 1, i - 1, f[i - 1] + a[i]);
		f[i] = t.query(1, 0, n, max(i - k, 0ll), i - 1) - INF;
	}
	printf("%lld\n", f[n] + 1ll * ((n - 1) / k + 1) * INF);
	
	return 0;
}

WA
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define pb emplace_back
#define int LL

using namespace std;
//using namespace __gnu_pbds;
using LL = long long;
using PII = pair<int, int>;

const int N = 1e6 + 10;
const LL INF = 1e12;
int n, k, stk[N], tt;
LL a[N], f[N];

struct Segtree {
	struct SegNode {
		int l, r;
		LL val, add;
	} tr[N << 2];
	
	void pushup(int u) {
		tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val);
	}
	
	void settag(int p, int v) {
		tr[p].add += v;
		tr[p].val += v;
	}
	
	void pushdown(int p) {
		if (tr[p].add) {
			settag(p << 1, tr[p].add);
			settag(p << 1 | 1, tr[p].add);
			tr[p].add = 0;
		}
	}
	
	void build(int p, int l, int r) {
		tr[p].l = l, tr[p].r = r;
		if (l == r) return ;
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	
	void modify(int p, int l, int r, int d) {
		// [l, r] += d;
		if (tr[p].l >= l && tr[p].r <= r) {
			settag(p, d);
			return ;
		}
		pushdown(p); // 不是单点
		int mid = tr[p].l + tr[p].r >> 1;
		if (l <= mid) modify(p << 1, l, r, d);
		if (r > mid) modify(p << 1 | 1, l, r, d);
		pushup(p);
	}
	
	LL query_max(int p, int l, int r) {
		if (tr[p].l >= l && tr[p].r <= r) return tr[p].val;
		pushdown(p);
		int mid = tr[p].l + tr[p].r >> 1;
		LL ans = -LONG_LONG_MAX;
		if (l <= mid) ans = max(ans, query_max(p << 1, l, r));
		if (r > mid) ans = max(ans, query_max(p << 1 | 1, l, r));
		return ans;
	}
} t;

signed main() {
	scanf("%lld%lld", &n, &k);
	for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
	// f[i] = max(f[j] + maxA(j + 1, i))
	// seg -> the max value of (f[j] + maxA(j + 1, i))
	t.build(1, 1, n);
	for (int i = 1; i <= n; i ++ ) {
		while (tt && a[stk[tt]] <= a[i]) {
			t.modify(1, stk[tt - 1], stk[tt] - 1, a[i] - a[stk[tt]]);
			-- tt;
		}
		stk[ ++ tt] = i;
		t.modify(1, i - 1, i - 1, f[i - 1] + a[i]);
		f[i] = t.query_max(1, max(i - k, 0ll), i - 1) - INF;
	}
	printf("%lld\n", f[n] + 1ll * ((n - 1) / k + 1) * INF);
	
	return 0;
}