洛谷1966 [NOIP2013]火柴排队

题意

有两个序列 $a,b$ ，可以把 $b$ 中相邻的数交换，使得 $\sum (a_i-b_i)^2$ 最小。问最少要交换几次？

题解

可以发现最小的情况就是 $a,b$ 中数字的大小顺序相同，所以离散化后建立 $a$ 中大小在 $b$ 的对应关系 $s$ ，求 $s$ 的逆序对个数即可。

#include<bits/stdc++.h>
#define ha 99999997

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=100005;
int n,a[N],b[N],c[N],d[N],s[N],t[N];

inline void add(int x,int y) { for (;x<=n;x+=x&-x) t[x]=(t[x]+y)%ha; }

inline int query(int x)
{
    int ans=0;
    for (;x;x-=x&-x) ans=(ans+t[x])%ha;
    return ans;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=n;i++) b[i]=read(),c[i]=d[i]=i;
    sort(c+1,c+n+1,[](int x,int y){ return a[x]<a[y]; });
    sort(d+1,d+n+1,[](int x,int y){ return b[x]<b[y]; });
    for (int i=1;i<=n;i++) s[c[i]]=d[i];
    int ans=0;
    for (int i=n;i;i--)
    {
        ans=(ans+query(s[i]-1))%ha;
        add(s[i],1);
    }
    return !printf("%d",ans);
}