题解：
将总距离表达式展开，尝试化简。发现平方的和是不变的，变的只有乘积，使Σaibi最大即可保证距离最小，自然想到最大的a让最大的b乘的贪心想法，即最终的顺序是a和b都从小到大（或从大到小）一一对应。尝试证明。
对于顺序的贪心证明，可从一步步调整入手。即假设存在ax>ay,bx>by，若x与x相对，答案为axbx+ayby；若x与y相对，则答案为axby+aybx，作差提取公因式可发现前者大于后者，故知答案序列必为顺序对应。
工作没有结束，题目并不要求最小的距离值，而是最小相邻交换次数。发现两个序列的交换是独立的（寻找性质），即可以先完成第一个序列的所有交换，再完成第二个序列的所有交换。找到这个性质后可以很大程度上简化思考（不然容易想破头皮也得不出结论）。对于同时处理两个序列的交换，我们还是更倾向于处理一个序列的交换。故尝试证明两个序列的交换可以等价到一个序列的交换。记两个序列分别为A、B序列，在做完A序列的交换后，发现接下来要在B序列做的所有交换按顺序对A序列做的话，最终A、B序列的对应关系是一样的，故我们只处理一个序列交换即可。
由于序列可以离散化，且离散化后两序列值域一样，不妨做个离散化，将序列中数的对应关系简化为相等关系，那么现在问题变为求一个序列A排成另一个序列B的最小交换次数。再做个简化，我们给B序列上的数从第一个位置开始按顺序标上编号，再把A序列的值改为这个值在B序列上的编号，则问题又转化为求一个序列A从小到大排成顺序的最小交换次数。
接下来一段时间可能想不出什么新东西了，不妨分析一下题目提到的操作：交换相邻两个数。思考这个操作在与题目有关的知识点上的意义：在排序里，交换相邻两个数可以消灭且只消灭一个相邻异序对。于是我们又找到了新的入手点。最后的顺序的异序对的个数为0，而一个操作最多消灭一个相邻异序对。异序对一定会相邻吗？思考一下，发现若存在异序对，则必会存在一个相邻异序对（考虑一对异序对a,b，设a，b之间没有相邻异序对，则a,b之间的数必从小到大排好了序，发现这个有序区间的端点必定有一个会与a或b组成一个相邻异序对），可发现最少操作次数即等于异序对个数。可用归并排序nlogn时间求出。
时间复杂度：O（n log n）
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 const int N=1e5+5; 8 9 struct node{ 10 int num,ord,li; 11 }a[N],b[N]; 12 13 inline int read() 14 { 15 int x=0; 16 char ch=getchar(); 17 while(!isdigit(ch)) 18 ch=getchar(); 19 while(isdigit(ch)) 20 x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); 21 return x; 22 } 23 24 int n,xord[N],xu[N],ins[N]; 25 26 long long mod=1e8-3,ans; 27 28 inline bool cmp1(const node &a,const node &b) 29 { 30 return a.num<b.num; 31 } 32 33 inline bool cmp2(const node &a,const node &b) 34 { 35 return a.ord<b.ord; 36 } 37 38 long long rev(int l,int r) 39 { 40 if(l==r) 41 return 0; 42 if(l+1==r) 43 { 44 if(xu[l]>xu[r]) 45 { 46 swap(xu[l],xu[r]); 47 return 1; 48 } 49 return 0; 50 } 51 int mid=(l+r)>>1; 52 long long ret=rev(l,mid)+rev(mid+1,r); 53 for(int i=l;i<=r;++i) 54 ins[i]=xu[i]; 55 int ll=l,rr=mid+1,cnt=l; 56 while(ll<=mid&&rr<=r&&cnt<=r) 57 { 58 if(ins[ll]<ins[rr]) 59 xu[cnt++]=ins[ll++]; 60 else 61 { 62 xu[cnt++]=ins[rr++]; 63 ret+=mid-ll+1; 64 } 65 } 66 if(cnt<=r) 67 { 68 while(ll<=mid) 69 xu[cnt++]=ins[ll++]; 70 while(rr<=r) 71 xu[cnt++]=ins[rr++]; 72 } 73 return ret%mod; 74 } 75 76 int main() 77 { 78 n=read(); 79 for(int i=1;i<=n;++i) 80 a[i].num=read(),a[i].ord=i; 81 for(int i=1;i<=n;++i) 82 b[i].num=read(),b[i].ord=i; 83 sort(a+1,a+n+1,cmp1); 84 sort(b+1,b+n+1,cmp1); 85 for(int i=1;i<=n;++i) 86 a[i].li=b[i].li=i; 87 sort(a+1,a+n+1,cmp2); 88 sort(b+1,b+n+1,cmp2); 89 for(int i=1;i<=n;++i) 90 xord[a[i].li]=i; 91 for(int i=1;i<=n;++i) 92 xu[i]=xord[b[i].li]; 93 printf("%lld",rev(1,n)); 94 return 0; 95 }
什么？你不会归并排序求逆序对？戳：逆序对小记
总之，这道题目在很多方面用了非常多简化。虽然很毒瘤，但一步步化到最后的感觉真的很奇妙。