[倍增] Genius acm

题解

给定一个长度为\(n\)的整数序列\(a\)，以及一个数\(t\)，和一个\(m\)，将\(a\)分成子序列，子序列中满足从中取出\(m\)对数（不能重复取，如果不够取到不能取为止），使得每一对数的差的平方和最大，
将这个最大值定义为序列的校验值，使得子序列的校验值小于等于\(t\)，问最少能够分成多少个子序列

（1）初始化\(p=1，r = l\)
（2）求出\([ l , r+p ]\)的校验值，如果\(<=t, r+=p,p*=2\),否则\(p/=2\)
（3）重复2，直到\(p=0\)
（4）以上的过程最多进行\(O（logn）\)次，每次循环都对$ r-l$ 排序，总体为O\(（n（logn）^2\)，每次求校验值的时候不需要快速排序，用类似归并排序的算法只需要对新增部分排序

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+100;
ll a[N],b[N],c[N],t;
int n,m,k,w;
inline void merge(int l,int mid,int r){
	int i=l,j=mid+1;
	for(int k = l; k <= r; k++)
		if(j > r || (i <= mid && b[i] <= b[j]))
			c[k] = b[i++];
		else
			c[k]=b[j++];
}
inline ll f(int l,int r){
	if(r>n)
		r=n;
	int min_m = min(m ,(r - l + 1) >> 1);
	for(int i = w + 1; i <= r; i++)
		b[i] = a[i];
	sort(b + w + 1,b + r + 1);
	merge(l,w,r);
	ll ans = 0;
	for(int i = 0; i < min_m; i++)
		ans+=(c[r-i]-c[l+i])*(c[r-i]-c[l+i]);
	return ans;
}
inline void work(){
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	w=1;
	int res=0,l=1,r=1;
	l=r=1;
	b[1]=a[1];
	while(l<=n){//当扩展的区间左端点合法
		int p=1;
		while(p){
			ll num=f(l,r+p);
			if(num<=t){
				w=r=min(r+p,n);
				for(int i = l; i <= r; i++)
					b[i]=c[i];
				if(r==n)
					break;
				p<<=1;
			}
			else
				p>>=1;
		}
		res++;
		l=r+1;
	}
	cout<<res<<endl;
}
int main(){
	cin>>k;
	while(k--){
		work();
	}
}

[倍增] Genius acm

原文：https://www.cnblogs.com/hhyx/p/13047364.html