题意
给出数列$a,b$，可交换各个数列中相邻的数，求最小的交换次数，使得$$\sum(a_i-b_i)^2$$最小，答案对$99999997$取模
数据范围：$1 \le n \le 1000000$
题解
对目标式化简
$$ \begin{aligned} \sum(a_i-b_i)^2 &= \sum(a_i^2-2a_ib_i+b_i^2) \\ &= \sum a_i^2 + \sum b_i^2 - 2\sum a_ib_i \end{aligned} $$
前两项的值为定值，对于第$3$项，为了最大，我们希望$a_i,b_i$分别在数列$a,b$的次序相同（即排序后$a_i$与$b_i$位于两个数列的同一位置，但我们显然没有必要将两个数列都进行排序，只需使两个数列的同一位置上的次序相同），因此我们将数列$a,b$离散化，然后使数列$b$与$a$相同，求$b$交换的次数（逆序对个数）即可，但是如何使数列$b$与$a$相同呢？
记$c[a[i]]=b[i]$，对数组$c$求逆序对，在求得逆序对之后，数组$c$会变得有序，即$c[i]=i$，回去看数组$c$的定义，则有$c[a[i]]=a[i]=b[i]$
求逆序对可用归并排序或树状数组
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000000+10;
const int mod=99999997;
int n;
int T[N],c[N];
int ans;
struct node{
int h,p;
inline bool operator < (const node& x){
return h<x.h;
}
} a[N],b[N];
inline int lowbit(int x){
return x&-x;
}
inline void update(int p,int v){
for(;p<=n;p+=lowbit(p))
T[p]+=v;
}
inline int query(int p){
int res=0;
for(;p;p-=lowbit(p))
res+=T[p];
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].h);
a[i].p=i;
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i].h);
b[i].p=i;
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
c[a[i].p]=b[i].p;
for(int i=n;i;i--){
(ans+=query(c[i]-1))%=mod;
update(c[i],1);
}
printf("%d",ans);
return 0;
}