为什么 $wqs$ 二分需要选择 决策点最前面的节点啊qaq

蒟蒻的代码：

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int, int>
#define mkp make_pair
#define sz(x) ((int) x.size())
#define be(x) x.begin()
#define en(x) x.end()
using namespace std;
const int N = 5e5;
int n, m, cnt[N];
ll dp[N], a[N], w[N], ans;
ll getval(int l, int r) {
	int mid = (l + r) >> 1; 
	return w[l - 1] + w[r] - w[mid] * 2 - a[mid] * (l + r - mid * 2 - 1);
}
int q[N], head, tail, las[N];
int get(int x, int y) { // y 更优的区间
	int l = 1, r = n, ans = n + 1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(dp[y] + getval(y + 1, mid) < dp[x] + getval(x + 1, mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	return ans;
}
int solve(ll x) {
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0, cnt[0] = 0;
	head = tail = 1, las[1] = n + 1; // [las_{i - 1}, las_i)
	L(i, 1, n) {
		while(head < tail && las[head] <= i) ++head;
		dp[i] = dp[q[head]] + x + getval(q[head] + 1, i), cnt[i] = cnt[q[head]] + 1;
		while(head < tail && get(q[tail], i) <= las[tail - 1]) --tail;
		las[tail] = get(q[tail], i), q[++tail] = i, las[tail] = n + 1;
	}
	return cnt[n];
}
void Main() {
	cin >> n >> m;
	L(i, 1, n) cin >> a[i], w[i] = w[i - 1] + a[i];
	ll l = 0, r = getval(1, n);
	while(l <= r) {
		ll mid = (l + r) >> 1;
		if(solve(mid) <= m) ans = dp[n] - mid * m, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Main();
	return 0;
}

在 get 函数中：

if(dp[y] + getval(y + 1, mid) < dp[x] + getval(x + 1, mid)) ans = mid, r = mid - 1;

改成

if(dp[y] + getval(y + 1, mid) <= dp[x] + getval(x + 1, mid)) ans = mid, r = mid - 1;

就会 WA 成 $20$ 分。

这是为什么啊 /kel /kel