题意
给定2个等长序列a、b，要求通过交换使
\[\sum_{i=1}^{n}(a_i-b_i)^2\]
最小。
分析
看着这个式子，我突然想到了方差。很明显，方差反应数据的波动程度，所以让数据集中就可以使方差变小了。而对应到这个公式，大方向就是让这两个数据尽可能接近。很容易想到分别排序，\(a_i,b_i\)就是对应数了（自己取的名字）。
这怎么证明呢？因为这个公式中带有平方，这会增加极限值对结果的贡献，所以要尽可能缩小最大差值（这也是方差教给我们的w）
那么要让a、b两个序列中的数对应，就要将a与b中的数建立一一对应的映射关系。这样，其中一个序列会作为排序的判定条件（也可以理解为判定大小的标准），而另一个序列就是要交换的序列了。这一过程其实就是离散化。
排序与求逆序对复杂度都是\(O(nlog_2n)\)，10w可过。
代码
#include<iostream>
#include<algorithm>
using namespace std;const int MAXN=100005,mod=99999997;
int n,m;
int p[MAXN],arr[MAXN],ans;
struct match{int value,order;
}a[MAXN],b[MAXN];bool comp(match m1,match m2)
{return m1.value<m2.value;
}int lowbit(int x)
{return x&(-x);
}void add(int x,int num)
{for(int i=x;i<=n;i+=lowbit(i))arr[i]+=num;return;
}int sum(int x)
{int temp=0;for(int i=x;i;i-=lowbit(i))temp+=arr[i];return temp;
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i].value,a[i].order=i;for(int i=1;i<=n;i++)cin>>b[i].value,b[i].order=i;//order记录顺序 sort(a+1,a+1+n,comp);sort(b+1,b+1+n,comp);//排序后就将两个序列建立对应关系了 for(int i=1;i<=n;i++)p[b[i].order]=a[i].order;for(int i=1;i<=n;i++)add(p[i],1),ans=(ans+i-sum(p[i]))%mod;//树状数组求逆序对 cout<<ans;return 0;
}
