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

· · 题解

首先，延续 F1 的思路，我们容易想到枚举中间点。

注意到我们并不需要钦定它是真正的中心点，因为如果它不是，那么真正的中心点的花费一定比它少。

然后我们就转化为了求其他颜色每种颜色到它的最小距离之和。

显然只有它左边和右边第一个有可能造成贡献。

因此我们把每种值单独提出来，显然对于左边/右边的段，他们分别取的是右边/左边的对应值，对于中间的段，显然中点和左边取左边的值，右边的取右边的值。

然后你会发现距离这个贡献是一个等差数列，经典套路了，线段树标记永久化轻松解决。

#include<bits/stdc++.h>
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
const int N=4e5+5;
int T,n,k,a[N];
vector<int> vec[N];
struct ST{ int tag1,cnt1,tag2,cnt2; }t[N<<2];
void build(int p,int l,int r){
    t[p].tag1=t[p].tag2=t[p].cnt1=t[p].cnt2=0;
    if(l==r) return;
    int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
void update1(int p,int l,int r,int ql,int qr,int w){
    if(ql<=l&&r<=qr){
        t[p].tag1+=w,++t[p].cnt1;
        return;
    }
    int mid=l+r>>1;
    if(qr<=mid) return update1(ls,l,mid,ql,qr,w);
    if(mid<ql) return update1(rs,mid+1,r,ql,qr,w);
    update1(ls,l,mid,ql,qr,w);
    update1(rs,mid+1,r,ql,qr,w+(mid-max(l,ql)+1));
}
void update2(int p,int l,int r,int ql,int qr,int w){
    if(ql<=l&&r<=qr){
        t[p].tag2+=w,++t[p].cnt2;
        return;
    }
    int mid=l+r>>1;
    if(qr<=mid) return update2(ls,l,mid,ql,qr,w);
    if(mid<ql) return update2(rs,mid+1,r,ql,qr,w);
    update2(ls,l,mid,ql,qr,w+(min(r,qr)-mid));
    update2(rs,mid+1,r,ql,qr,w);
}
int query(int p,int l,int r,int pos){
    if(l==r) return t[p].tag1+t[p].tag2;
    int mid=l+r>>1;
    if(pos<=mid) return query(ls,l,mid,pos)+t[p].tag1+t[p].cnt1*(pos-l)+t[p].tag2+t[p].cnt2*(r-pos);
    return query(rs,mid+1,r,pos)+t[p].tag1+t[p].cnt1*(pos-l)+t[p].tag2+t[p].cnt2*(r-pos);
}
void update(int l,int r){
    int mid=l+r>>1;
    update1(1,1,n,l,mid,0);
    update2(1,1,n,mid+1,r,0);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k;
        for(int i=1;i<=n;++i) cin>>a[i],vec[a[i]].emplace_back(i);
        build(1,1,n);
        for(int i=1;i<=k;++i){
            int L=vec[i].size();
            update2(1,1,n,1,vec[i][0],0);
            for(int j=1;j<L;++j) update(vec[i][j-1],vec[i][j]);
            update1(1,1,n,vec[i][L-1],n,0);
        }
        int ans=1e18;
        for(int i=1;i<=n;++i) ans=min(ans,query(1,1,n,i));
        if(k&1) ans-=((k>>1)*((k>>1)+1));
        else ans-=((k>>1)*((k>>1)-1)/2+(k>>1)*((k>>1)+1)/2);
        cout<<ans<<endl;
        for(int i=1;i<=k;++i) vec[i].clear(),vec[i].shrink_to_fit();
    }
    return 0;
}