hihocoder 1384 Genius ACM（倍增+归并）

题目链接

题意

给你三个整数 n ， m ， k n，m，k n，m，k 表示一个 n n n 个元素的集合 a i a_i ai​，分隔成最连续的若干段，求小段数，每段的校验值不超过k。

校验值计算公式，该段中选出若干对元素，每对元素（a，b）贡献为 ( b − a ) 2 (b-a)^2 (b−a)2，校验值为该段最大贡献和。

思路

设四个数 a &lt; b &lt; c &lt; d a &lt; b &lt; c &lt; d a<b<c<d

( d − a ) 2 + ( c − b ) 2 − ( ( d − b ) 2 + ( c − a ) 2 ) = … … &gt; 0 (d-a)^2+(c-b)^2 -((d-b)^2+(c-a)^2) = ……&gt;0 (d−a)2+(c−b)2−((d−b)2+(c−a)2)=……>0 所以选两边更优

问题可以变为，确定一个左端点，右端点能取多长。扩展右端点，可以倍增扩展。

• 左端点L固定，初始化R=L，P = 1，P即扩展长度。
• 求 [ L , R + P ] [L,R+P] [L,R+P]的校验值， &lt; = k ， 则 R + = P ， P ∗ = 2 ， 否 则 P / = 2 &lt;=k，则R+=P，P*=2，否则 P/=2 <=k，则R+=P，P∗=2，否则P/=2
• 重复上一步直到P为0，R即所求右端点，L更新为R+1。

一个小优化类似归并，求校验值时 [ L , R ] [L,R] [L,R]已经必然成立，使 [ L , R ] [L,R] [L,R]区间为升序，减少了每次 P / = 2 P/=2 P/=2时排序，那么只需排序 [ R + 1 , R + P ] [R+1,R+P] [R+1,R+P]，然后归并一下 [ L , R + P ] [L,R+P] [L,R+P]，可以使用merge函数减少代码量，第一次知道merge。

代码

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

#define ll long long

ll Rd(ll &_a){return scanf("%lld",&_a);}
ll rd(){ll _tmp; scanf("%lld",&_tmp); return _tmp;}

ll n, m, k;
ll v[500005], tmp[500005], fq[500005];

void sor(ll l, ll ind, ll r)
{
    for(ll i = ind+1; i <= r; ++i) tmp[i] = v[i];
    sort(tmp+ind+1,tmp+r+1);
    merge(v+l,v+ind+1,tmp+ind+1,tmp+r+1,fq);
    for(int i = 0; l+i <= r; ++i) tmp[l+i] = fq[i];
}

ll check(ll l, ll ind, ll r)
{
    ll sum = 0;
    sor(l,ind,r);
    for(ll i = min(m,(r-l+1)/2); i; --i)
    {
        sum += (tmp[l+i-1]-tmp[r-i+1])*(tmp[l+i-1]-tmp[r-i+1]);
        if(sum > k) return 0;
    }
    for(ll i = l; i <= r; ++i) v[i] = tmp[i];
    return 1;
}

int main()
{
    for(ll t = rd(); t; --t)
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        for(ll i = 1; i <= n; ++i) Rd(v[i]);
        ll l = 1, r, p, ans = 0;
        while(l <= n)
        {
            ++ans, p = 1, r = l; // 固定左端点l，r为已经确认满足的最大范围，p+r为试探范围
            while(p)
            {
                if(r+p <= n && check(l,r,r+p)) r += p, p <<= 1;
                else p >>= 1;
            }
            l = r+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}