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

· · 题解

题意

给定一个序列，可以交换相邻元素，问至少交换多少次使得存在一个子区间是一个 1 到 k 的排列。

思路

由 F1 的暴力做法得知，可以钦定一个位置为中心，其他期望出现在区间中的数向中间靠拢，计算过程就是统计每种数出现在中心的左或右的最近位置，看左右两边去哪个更优，最后减去多余的移动即可（就是不需要都移到中心位置，一个接一个就行）。

考虑如何优化这一过程。先对每种数分开观察，会发现每次的变化量的绝对值 \leq 1，即只有加 1，减 1，不变三种情况。如果两个相邻数之间的距离是偶数，那就有两个中心，从左到右就不变；否则是奇数时就只有一个中心。在中心之前，变化量为减 1；在中心之后，变化量为加 1。然后就好办了,用差分给区间的变化量赋值就行了。

实现简洁，代码如下

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=4e5+10;
int n,k,s,d,ans;
int a[maxn],lst[maxn],sum[maxn];
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        s=0,ans=1e18;
        cin>>n>>k;
        for(int i=1;i<=n;i++) lst[i]=sum[i]=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(!lst[a[i]]) s+=i-1;
            else
            {
                int pre=lst[a[i]],mid=(pre+i)/2;
                if((pre+i)&1) sum[mid]--,sum[mid+1]--;
                else sum[mid]-=2;
            }
            sum[i]+=2;
            lst[a[i]]=i;
        }
        d=-k;
        for(int i=1;i<=n;i++)
        {
            ans=min(ans,s);
            d+=sum[i],s+=d;
        }
        for(int i=1;i<=k;i++) ans-=abs(i-(k+1)/2);
        cout<<ans<<endl;
    }
}