题解：CF2085F2 Serval and Colorful Array (Hard Version)

· · 题解

思路

首先想到一个小结论：假如我们已经钦定好了最后要组成排列的所有数字，定义第 i 所在的位置为 p_i，那么如何让它们贴在一起的代价最小？显然是向 p 的中位数处靠拢，这下真读者自证不难了。

然后又发现了一个小结论：如果我们已经确定了 p 都要向 i 处靠拢，那么应该如何确定数组 p 呢？每种数字肯定都是越靠近 i 越好的,也就是 i 前后最接近 i 的数字是有用的，故我们定义数组 A_j 和 B_j 分别表示对于数字 j，在 i 和之前下标最大 j 和 i 之后下标最小的 j 是什么。

设 l=\lfloor\frac{m}{2}\rfloor,r=m-l 表示 i 左右的数字个数。假设 A,B 中下标小于等于 r 的都在 i 右边，那么这种选法对答案的贡献如下：

(\sum_{j=1}^{l}{(i-j+1)-A_{r+j}})+(\sum_{j=1}^{r}{B_j-(i+j)})

稍加整理，得到下式：

(\sum_{j=i-l+1}^{i}{j}-\sum_{j=i+1}^{i+r}{j}-\sum_{j=1}^{m}{A_j})+(\sum_{j=1}^{r}{A_j+B_j})

可以发现，如果 A,B 确定了，最终对答案的贡献就是前一个括号里的定值加上前 r 小的 A+B 的值。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10,inf=1e11,sgl=-2e11,sgr=2e11;
int n,m;
int w[N],a[N],b[N],suma;
int lst[N],nxt[N];
int root;
struct segmenttree{
    int pcnt;
    struct node{
        int ls,rs,siz,data;
    }t[N<<5];
    void push_up(int p){
        t[p].data=t[t[p].ls].data+t[t[p].rs].data;
        t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz;
    }
    void modify(int l,int r,int x,int &p,int d){
        if(!p){p=++pcnt;t[p].ls=t[p].rs=t[p].data=t[p].siz=0;}
        if(l==r){
            t[p].siz+=d;t[p].data+=d*x;return ;
        }
        int mid=l+r>>1;
        if(mid>=x)modify(l,mid,x,t[p].ls,d);
        else modify(mid+1,r,x,t[p].rs,d);
        push_up(p);
    }
    int query(int l,int r,int p,int k){
        if(!p)return 0;
        if(l==r)return t[p].data/t[p].siz*k;
        int ret=0,mid=l+r>>1;
        if(t[t[p].ls].siz>=k)ret=query(l,mid,t[p].ls,k);
        else ret=query(mid+1,r,t[p].rs,k-t[t[p].ls].siz)+t[t[p].ls].data;
        return ret;
    }
}s;
void push(int a,int b,int d){
    s.modify(sgl,sgr,a+b,root,d);suma+=a*d;
}
int ans=inf;
int Galse(int l,int r){
    if(l>r)return 0;
    return (l+r)*(r-l+1)/2;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)nxt[i]=0;
    for(int i=1;i<=m;i++)a[i]=b[i]=lst[i]=0;
    suma=s.pcnt=root=0;
    ans=inf;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        nxt[lst[w[i]]]=i;
        lst[w[i]]=i;
    }
    for(int i=1;i<=n;i++)if(!nxt[i])nxt[i]=inf;
    for(int i=1;i<=m;i++)a[i]=-inf;
    for(int i=1;i<=n;i++)if(!b[w[i]])b[w[i]]=i;
    for(int i=1;i<=m;i++)push(a[i],b[i],1);
    int l=m/2,r=m-l;
    for(int i=1;i<=n;i++){
        push(a[w[i]],b[w[i]],-1);
        a[w[i]]=b[w[i]];b[w[i]]=nxt[i];
        push(a[w[i]],b[w[i]],1);
        ans=min(ans,Galse(i-l+1,i)-Galse(i+1,i+r)-suma+s.query(sgl,sgr,root,r));
    }
    cout<<ans<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}