看到题解区没有分块做法，于是补一篇分块题解。

分块大法好！

题目描述

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

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

现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$。

我们要把 $A$ 分成若干段，使得每一段的“校验值”都不超过 $T$。

求最少需要分成几段。

Part 1. 贪心

对于一个集合 $S$，容易用邻项交换证明，应该令最大和次大构成一对，次大和次小构成一对……这样得到的“校验值”最大。于是可以 $O(|S|\log |S|)$ 求出集合 $S$ 的校验值。

为了让数列 $A$ 分成的段数最少，每一段都应该在“校验值”不超过 $T$ 的前提下，尽量包含更多的数。

于是现在需要高效解决的问题为：当确定一个左端点 $L$ 之后，右端点 $R$ 在满足 $A[L]\sim A[R]$ 的校验值不超过 $T$ 的前提下，最大能取到多少。

当遇到像“校验值”这种奇怪的信息，无法高效地维护扩展、合并时，我们可以考虑暴力的分块。

Part 2. 分块

像本题的倍增做法一样，分块可以与右端点 $R$ 扩展的长度相适应。

做法相当简单粗暴：

当确定一个左端点 $L$ 之后，
1. 在 $L$ 所在的块内，逐个右移 $R$，实时 $O(|S|\log |S|)$ 求出 $A[L]\sim A[R]$ 的校验值并与 $T$ 比较。若校验值大于 $T$，则令 $R$ 左移一个，结束；否则，重复此步直至 $R$ 到达块内的右端点，进行第 $2$ 步。
2. 逐块右移 $R$，实时 $O(|S|\log |S|)$ 求出 $A[L]\sim A[R]$ 的校验值并与 $T$ 比较。若校验值大于 $T$，则令 $R$ 左移一块，进行第 $3$ 步；否则，重复此步直至 $R$ 到达 $N$，结束。
3. 逐个右移 $R$，实时 $O(|S|\log |S|)$ 求出 $A[L]\sim A[R]$ 的校验值并与 $T$ 比较，直至校验值大于 $T$。然后令 $R$ 左移一个，结束。

Part 3. 归并排序优化

$O(N \log N)$ 预处理每个块的内部排序后的结果，合并集合时使用归并排序的思想，可以优化到 $O(|S|)$ 实时求出校验值。

时间复杂度

记 $n_i$ 表示分成的第 $i$ 段的长度。$\sum\limits n_i=N$。

$O(\sum\limits n_i\sqrt N)=O(N\sqrt N)$。

C++ 代码

#pragma GCC optimize(2)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e5+10,B=710;
int k,n,m,ans;
ll t,a[N];
int len,l[B],r[B];
ll b[B][B];
int clen,dlen;
ll c[N],d[N];

inline ll read()
{
    ll res=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res;
}

inline int get(int x)
{
    return (x-1)/len+1;
}

inline void merge(int elen,ll e[])
{
    dlen=0;
    int i=1,j=1;
    while(i<=clen && j<=elen)
    {
        if(c[i]<=e[j])
        {
            d[++dlen]=c[i];
            i++;
        }
        else
        {
            d[++dlen]=e[j];
            j++;
        }
    }
    while(i<=clen)
    {
        d[++dlen]=c[i];
        i++;
    }
    while(j<=elen)
    {
        d[++dlen]=e[j];
        j++;
    }
    return ;
}

inline ll calc()
{
    ll res=0;
    for(int i=1,j=dlen;i<=m && i<j;i++,j--) res+=(d[j]-d[i])*(d[j]-d[i]);
    return res;
}

inline void copy()
{
    clen=dlen;
    for(int i=1;i<=dlen;i++) c[i]=d[i];
    return ;
}

inline int solve(int st)
{
    int ed=st;
    clen=1;
    c[1]=a[st];
    while(ed+1<=n && get(st)==get(ed+1))
    {
        ll e[3];
        e[1]=a[ed+1];
        merge(1,e);
        if(calc()>t) return ed;
        copy();
        ed++;
    }
    while(get(ed)+1<=get(n))
    {
        merge(r[get(ed)+1]-l[get(ed)+1]+1,b[get(ed)+1]);
        if(calc()>t) break;
        copy();
        ed=r[get(ed)+1];
    }
    while(ed+1<=n)
    {
        ll e[3];
        e[1]=a[ed+1];
        merge(1,e);
        if(calc()>t) return ed;
        copy();
        ed++;
    }
    return ed;
}

int main()
{
    k=read();
    while(k--)
    {
        ans=0;

        n=read(),m=read(),t=read();
        for(int i=1;i<=n;i++) a[i]=read();

        len=sqrt(n);
        for(int i=1;i<=get(n);i++)
        {
            l[i]=len*(i-1)+1,r[i]=min(len*i,n);
            for(int j=l[i];j<=r[i];j++) b[i][j-l[i]+1]=a[j];
            sort(b[i]+1,b[i]+r[i]-l[i]+2);
        }

        for(int i=1;i<=n;i=solve(i)+1) ans++;

        printf("%d\n",ans);
    }
    return 0;
}