【题意】两列n个火柴，分别有高度ai和bi（同一列高度互不相同），每次可以交换一列中的两个相邻火柴，定义距离为∑(ai-bi)^2，求使距离最小的最少交换次数，n<=10^5。

【算法】逆序对

【题解】∑(ai-bi)^2=∑ai^2+∑bi^2-∑ai*bi，其中∑ai^2和∑bi^2为常数，则要使∑ai*bi最大。

对于两个序列的∑ai*bi，根据排序不等式，有逆序和<=乱序和<=正序和。（可以理解为两数离得越近，乘积越大）

将两序列各自离散化后，问题转化为使两序列每位数字相等。

为了方便统计，换种角度说就是A数组的每个数字需要移动到一个对应的位置，所以我们设置C数组表示A数组中每个数应该去的位置。

（具体操作中最方便的方法是：A和B排序，然后C[A[i].id]=B[i].id）

那么实际上我们就是要通过交换使C数组升序排列，问题转化为通过最少次交换相邻数字使一个序列升序排列。

要使交换次数最少，就使每次交换消除一个逆序对。如果不存在相邻逆序对，可以证明序列已经升序排列。

所以答案是逆序对数，可以使用树状数组或归并排序求逆序对，复杂度O(n log n)。

#include
      
       #include
       
        #include
        
         #include
         
          #define lowbit(x) x&-x#define ll long longusing namespace std;const int maxn=100010,MOD=99999997;//ji de qu moint read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}int n,c[maxn],A[maxn];struct cyc{
    int num,id;}a[maxn],b[maxn];bool cmp1(cyc a,cyc b){
    return a.num
          
           =1;i-=lowbit(i))ans+=c[i];return ans;}int main(){     n=read();     for(int i=1;i<=n;i++)a[i].num=read(),a[i].id=i;     for(int i=1;i<=n;i++)b[i].num=read(),b[i].id=i;     sort(a+1,a+n+1,cmp1);sort(b+1,b+n+1,cmp1);     for(int i=1;i<=n;i++)A[a[i].id]=b[i].id;     ll ans=0;     for(int i=1;i<=n;i++){         insert(A[i]);         ans+=i-query(A[i]);//    }    printf("%lld",ans%MOD);    return 0;}
          
         
        
       
      

记得取模！