[hihocoder #1384] Genius ACM 解题报告（倍增）

题目链接：http://hihocoder.com/problemset/problem/1384

题目大意：

给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:

从集合 S 中取出 M 对数(即 2∗M 个数，不能重复使用集合中的数，如果 S 中的整数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 S 的“校验值”。

现在给定一个长度为 N 的数列 A 以及一个整数 T。我们要把 A 分成若干段，使得每一段的“校验值”都不超过 T。求最少需要分成几段。

题解：

现在对于一个数列，它的校验值就是排序之后第一大的和第一小的配对，第二大的和第二小的配对....

现在我们让段数尽可能少，就是让每段尽可能长

于是问题就是转化成了确定区间右端点L，左端点最远是哪里的问题

二分显然是可行的，但是这样常数太大了，我们考虑倍增

1.初始化p=1,R=L

2.求出[L,R+p]这段区间的校验值，如果<=k，那么L+=p，p<<=1，否则p>>=1

3.重复上一步直到p=0退出，更新L=R+1

怎么求校验值呢？一个显然的方法就是我们每次都排序

这样显然有大量浪费

考虑我们每次计算[L,R+p]的时候归并处理，时间复杂度降到$O(nlogn)$

#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;

const int N=5e5+15;
int T,n,m;
ll k;
ll a[N],b[N],c[N];
inline ll read()
{
    char ch=getchar();
    ll s=0,f=1;
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
void mergy(int l,int r,int mid)
{
    int i=l,j=mid;
    for (int k=l;k<=r;k++)
    {
        if ((b[i]<b[j]&&i<mid)||j>r) c[k]=b[i++];
        else c[k]=b[j++];
    }
}
int L,R;
void merge_sort(int l,int r)
{
    for (int i=R+1;i<=r;i++) b[i]=a[i];
    sort(b+R+1,b+r+1);
    mergy(l,r,R+1);
}
ll calc(int l,int r)
{
    merge_sort(l,r);
    ll re=0,cnt=0;
    for(int i=l,j=r;i<j;i++,j--)
    {
        re+=1ll*(c[i]-c[j])*(c[i]-c[j]);
        cnt++;
        if(cnt==m) break;
    }
    return re;
}
int solve()
{
    int p=1;
    R=L;b[L]=a[L];
    while (p)
    {
        if (R+p<=n&&calc(L,R+p)<=k) 
        {
            R+=p;
            p<<=1;
            for (int i=L;i<=R;i++) b[i]=c[i];
        }
        else p>>=1;
        if (R>n) break;
    }
    return R;
}
int main()
{
    T=read();
    while (T--)
    {
        n=read();m=read();k=read();
        for (int i=1;i<=n;i++) a[i]=read();
        int re=0;
        L=1;
        while (L<=n)
        {
            int k=solve();
            L=k+1;
            re++;
        }
        printf("%d
",re);
    }
    return 0;
}