首先，可以显然证明：要让 每对数的差的平方和 $S$ 最大，一定是选最大的 $M$ 个数和最小的 $M$ 个数。

$证明：$

设四个数 $a,b,c,d$ ，使 $a>b>c>d$ ，就有两种方案

$①-②$ 得 $2ac+2bd-2ad-2bc ③$

因式分解 $③$ 得 $2(a-b)(c-d)$ ，由 $a>b>c>d$ 得$①-② >0, ①>②$

所以 $(a-d)^2 + (b-c)^2$ 更大！

$证毕$

那么怎么分段呢？

贪心，从头开始对 $A$ 分段，让每一段尽量长，一直分到结尾，显然是最优的！

固定一个左端点 $l$ ，倍增去找一个右端点 $r$ ，排序去找最大的 $M$ 个和最小的 $M$ 个。

排序的时候因为以前的都已经排好序，可以只排序新加进来的，然后归并排序即可。

tips: 可以用 #include<algorithm> 中的 merge 函数，不用手写归并！

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

inline long long read(){
	long long x=0; char c=getchar();
	while (c<'0'||c>'9'){
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x;
}

long long T,n,m,k,a[500005];
long long st[500005],f[500005];//st[i]是待归并的数组，f[i]是归并完成的数组

inline bool check(int L,int MID,int R){
	if (R>n) return 0;
	for (int i=MID;i<=R;i++){
		st[i]=a[i];
	}
	sort(st+MID,st+R+1);
	merge(st+L,st+MID, st+MID,st+R+1, f+L);
	
	int l=L,r=R,cnt=0;
	long long sum=0; 
	while (l<r && sum<=k && ++cnt<=m){
		sum+=1ll*(f[r]-f[l])*(f[r]-f[l]);
		l++; r--;
	}
	if (sum<=k){
		for (int i=L;i<=R;i++){
			st[i]=f[i];
		}
	}
	return sum<=k;
}

int main(){
	T=read();
	while (T--){
		n=read(); m=read(); k=read();
		for (int i=1;i<=n;i++){
			a[i]=read();
		}
		int l=1,r=1,bin=1,cnt=0;
		st[l]=a[l];
		while (r<=n){
			if (!bin){//另起一段
				cnt++;
				l=r=r+1;
			}
			if (check(l,r+1,r+(1<<bin)-1)){//是否可继续增加倍增范围
				r=r+(1<<bin)-1;
				bin++;//范围增加
			}else bin--;//范围缩短
		}
		printf("%d\n",cnt);
	}
	return 0;
}

这个代码的细节太多了 挑了半天才跳出来

czp想看我代码，那我就放上吧。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
#define N 700005
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e-'0');
		e=getchar();
	}
	return x*y;
}
int T,n,m,k,a[N];
int b[N],c[N],d[N],mx;
bool check(int l,int r,int len) {

	for(int i=l; i<=r; ++i) {
		b[i-l+1]=a[i];
	}
	for(int i=r+1; i<=r+len; ++i) {
		c[i-r]=a[i];
	}
	if(r+len>mx)sort(c+1,c+1+len);
	int x,y,cnt;
	x=y=1,cnt=0;
	while(x<=r-l+1||y<=len) {
		++cnt;
		if(x>r-l+1)d[cnt]=c[y],++y;
		else if(y>len)d[cnt]=b[x],++x;
		else {
			
			if(b[x]<c[y]) {
				d[cnt]=b[x],++x;
			} else {
				d[cnt]=c[y],++y;
			}
		}
	}
	int sum=0;
	for(int i=1; i<=m&&i<cnt-i+1; ++i) {
		sum+=(d[cnt-i+1]-d[i])*(d[cnt-i+1]-d[i]);
	}
	if(sum<=k) {
		for(int i=1; i<=cnt; ++i) {
			a[i+l-1]=d[i];
		}
		return 1;
	}
	return 0;
}
int l,r,len,ans;
signed main() {
	R(T);
	while(T--) {
		R(n),R(m),R(k);
		for(int i=1; i<=n; ++i) {
			R(a[i]);
		}
		l=1,ans=0,mx=0;
		while(l<=n) {
			r=l,len=1;
			while(len&&r<=n) {
				if(check(l,r,len)) {
					r+=len,len<<=1;
					mx=max(mx,len);
				} else {
					len>>=1;
				}
			}
			l=r+1,++ans;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

首先，可以显然证明：要让 每对数的差的平方和 $S$ 最大，一定是选最大的 $M$ 个数和最小的 $M$ 个数。

然后我们对于每一个位置 $i$ 去向后扩展能扩展的最大位置，然后记录

扩展的时候可以使用倍增+类归并排序的东西

注意：倍增的时候不要从大到小枚举 $2^i$ 的长度，因为若答案较小可能会超时

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int N=6*1e5+10;
int T,n,m,k,ans=0,maxn=-2e9;
int a[N],t[N],b[N],c[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
void clr(){
	ans=0;
	maxn=-2e9;
}
bool check(int L,int oR,int nR){
//	memset(b,0,sizeof(b)),memset(c,0,sizeof(c)),memset(t,0,sizeof(t));
	for(int p=L;p<oR;p++) b[p]=a[p];
	for(int p=oR;p<=nR;p++) c[p]=a[p];
	sort(c+oR,c+nR+1);
//	for(int u=1;u<=n;u++) cout<<b[u]<<" "<<c[u]<<endl;
	int i=L,j=oR,cnt=L;
//	cout<<"\nij:"<<i<<" "<<j<<" "<<cnt<<" "<<L<<" "<<oR<<" "<<nR<<"\n";
	while(i<oR&&j<=nR){
		if(b[i]<=c[j]) t[cnt++]=b[i++];
//		cout<<"\nij:"<<i<<" "<<j<<" "<<cnt<<"\n";
//		for(int u=1;u<=n;u++) cout<<t[u]<<" ";
		if(b[i]>c[j]) t[cnt++]=c[j++];
//		cout<<"\nij:"<<i<<" "<<j<<" "<<cnt<<"\n";
//		for(int u=1;u<=n;u++) cout<<t[u]<<" ";
	}
	while(i<oR) t[cnt++]=b[i++];
	while(j<=nR) t[cnt++]=c[j++];
//	for(int u=1;u<=n;u++) cout<<t[u]<<" ";
//	puts("");
	i=L,j=nR;
	int sum=0,ret=1;
	while(i<j&&ret<=m){
//		cout<<"sum:"<<i<<" "<<j<<" "<<ret<<" "<<sum<<endl;
		sum+=(t[i]-t[j])*(t[i]-t[j]);
		i++,j--;
		ret++;
	}
//	cout<<"final:"<<sum<<endl;
	if(sum<=k)	for(int p=L;p<=nR;p++) a[p]=t[p];
	return sum<=k;
}
int finds(int k){
	int now=k,i=1;
	while(i&&now<=n){
		if(check(k,now,now+i)){
			now+=i;
			i<<=1;
		}
		else i>>=1;
	}
	return now;
}
signed main(){
	T=reads();
	while(T--){
		clr();
		n=reads(),m=reads(),k=reads();
		for(int i=1;i<=n;i++) a[i]=reads();
		int now=1;
		while(now<=n){
			int x=finds(now);
//			cout<<now<<"->"<<x<<"\n";
			now=x+1;
			ans++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
1
5 1 49
8 2 1 7 9
*/