0x06 倍增

试想这样一个问题：
给定一个长度为 N 的数列 A，然后进行若干次询问，每次给定一个整数 T，求出最大的 K，满足 。
你的算法必须是在线的（必须即时回答每一个询问，不能等待收到所有询问后再统一处理）假设 。

1. 暴力枚举，每次询问花费的时间与答案有关，最坏情况下为 #card=math&code=O%28N%29&id=ppbQO)。
2. 二分，首先预处理出 A 数组前缀和 S，然后通过二分来找到最大的 K，复杂度 #card=math&code=O%28%5Clog%20N%29&id=dUnCQ)。但是如果 K 本身非常小，那么这样做还不如从前向后枚举。
3. 倍增算法。

我们可以设计一种倍增算法：

1. 令 p=1,k=0,sum=0
2. 比较 「A 数组中 k 之后的 p 个数之和」与 T 的关系。
   1. 如果 sum + S[k + p] - S[k] <= T，则令 sum += S[k + p] - S[k], k += p, p *= 2，即累加后面 p 个数，然后将步长 p 增加一倍。
   2. 如果 sum + S[k + p] - S[k] > T，则令 p /= 2，缩小步长。
3. 重复上一步，直到 p 的值变为 0，此时 k 就是答案。

天才ACM

给定一个整数 ，对于任意一个整数集合 ，定义“校验值”如下:
从集合 中取出 对数(即 个数，不能重复使用集合中的数，如果 中的整数不够 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 的“校验值”。
现在给定一个长度为 的数列 以及一个整数 。
我们要把 分成若干段，使得每一段的“校验值”都不超过 。
求最少需要分成几段。
输入格式
第一行输入整数 ，代表有 组测试数据。
对于每组测试数据，第一行包含三个整数 。
第二行包含 个整数，表示数列。
输出格式
对于每组测试数据，输出其答案，每个答案占一行。
数据范围
,
,
,

输入样例：

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9

输出样例：

2
1

首先，对于一个集合 S，显然应该取 S 中最大的 M 个数和最小的 M 个数配对，最大和最小、次大和次小。然后从头开始，尽可能的使每一段在满足「校验值」不超过 T 的前提下，长度更长。

问题转换：当确定一个左端点 L 之后，右端点 R 在满足 A[L] ~ A[R] 的 「校验值」不超过 T 的前提下，最大能取到多少。

长度为 N 的序列求解 「校验值」，需要先排序再配对，复杂度为 #card=math&code=O%28N%5Clog%20N%29&id=f6TGp)。如果每次求解 R 使用二分判定，单次复杂度为 #card=math&code=O%28N%5Clog%20%5E2%20N%29&id=ptr6z)。这样做整体复杂度可能会很高，因为里面重复进行了很多次排序。

所以可以使用倍增的方法，R 每次向右移动，只对移动后的这部分排序即可。

1. 初始化 p = 1, R = L
2. 求出 [L, R + p] 这一段区间的 「校验值」，如果小于等于 T，R += p, p *= 2 ；否则 p /= 2
3. 不断重复上一步，直到 p 的值变为 0.

以上这个过程最多只会循环 #card=math&code=O%28%5Clog%20N%29&id=j0LM5) 次，每次循环对长为 #card=math&code=O%28R-L%29&id=Hynnf) 的一段进行排序，最后累计扩展长度为 N，所以总体复杂度是 #card=math&code=O%28N%5Clog%5E2%20N%29&id=rLiwl)

实际上，只需要对新增的部分排序，然后合并新旧两段即可，这样总体复杂度可以降低到 #card=math&code=O%28N%5Clog%20N%29&id=F4UhB)。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 500010;
int k, n, m, a[N], b[N], c[N];
ll t;
void merge(int l,int mid,int r){
    int i = l, j = mid + 1, p = l;
    while(i <= mid && j <= r){
        if(b[i] <= b[j])
            c[p++] = b[i++];
        else
            c[p++] = b[j++];
    }
    while(i <= mid)
        c[p++] = b[i++];
    while(j <= r)
        c[p++] = b[j++];
}
inline ll S(int x) { return 1ll * x * x; }
ll calc(int l,int mid,int r){
    int len = r - l + 1;
    for (int i = l; i <= r;i++)
        b[i] = a[i];
    sort(b + mid + 1, b + r + 1);
    merge(l, mid, r);
    ll res = 0;
    for (int i = 0; i < min(len / 2,m);i++){
        res += S(c[r - i] - c[l + i]);
    }
    return res;
}
int solve(){
    int res = 0;
    int p = 1, L = 1, R = 1;
    while(L <= n){
        int nR = min(R + p, n);
        if(calc(L,R,nR) <= t){ // 可行
            for (int i = L; i <= nR;i++)
                a[i] = c[i];
            R = nR;
            p *= 2;
            if(R + p > n)
                p = n - R;
        }else{
            p /= 2;
        }
        if(p == 0){
            res++;
            L = R + 1;
            R = L;
            p = 1;
        }
    }
    return res;
}
int main()
{
    scanf("%d", &k);
    while(k--){
        scanf("%d%d%lld", &n, &m, &t);
        for (int i = 1; i <= n;i++)
            scanf("%d", &a[i]);
        printf("%d\n",solve());
    }
    return 0;
}