WQS 二分在统计选择数量时是不是最好强制定一个方向。

比如此题，我先放代码：

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1e6+10;
const ll INF=1e12;
int n,m;
ll dp[N],g[N],s[N];
int q[N];
void init(){
	memset(dp,0,sizeof(dp));
	memset(g,0,sizeof(g));
}
ll k;
#define b(i) (dp[i]+s[i]*s[i])
ld slope(int i,int j){
	return s[i]==s[j]?1.0*(b(j)-b(i))*INF:1.0*(b(j)-b(i))/(s[j]-s[i]);
}
void solve(){
	int head=1,tail=0;
	q[++tail]=0;
	for(int i=1;i<=n;i++){
		while(head < tail && slope(q[head],q[head+1]) < (ld)(2.0*s[i]))head++;
		int j=q[head];
		dp[i]=dp[j]+(s[i]-s[j])*(s[i]-s[j])-k;
		g[i]=g[j]+1;
		while(head < tail && slope(q[tail-1],q[tail]) > slope(q[tail],i))tail--;
		q[++tail]=i;
	}
}

int main(){
	//freopen("data.in","r",stdin);
	//	freopen(".out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)s[i]=read()+s[i-1];
	ll l=-INF,r=0,res=1;
	while(l<=r){
		ll mid=(l+r)/2;
		init();
		k=mid;
		solve();
		if(g[n] <= m)res=mid,l=mid+1;
		else r=mid-1;
	}
	k=res;
	solve();
	//assert(g[n]==m);
	cout<<(m*(dp[n]+k*m) - s[n]*s[n])<<"\n";
	fprintf(stderr,"%lld %lld %lld %lld\n",res,dp[n],s[n],dp[n]+g[n]*k);
	return 0;
}

然后斜率优化那一段是没有加上关于 $g$ 的判定的，那 $g$ 出来的是不是一个较为随机的值。

此时 WQS 二分会导致可能二分不到 $m$ 。

于是那个 assert 就会 RE（我试过第 $8$ 个点）。

那为什么最后还原 $dp$ 时用的是 $m$ 而不是 $g(n)$ ？

thx.