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;
}