题目：https://www.luogu.org/problemnew/show/P1966
首先假想是不是两边都按升序排列是差的和最小的。
举了几个例子发现没问题。具体分析了一下，如果有两个相邻元素在两列的对应位置都是升序，交换一下只会不变或变得更差。（可以分类看，比如a1<b1,a2<b1或a1<b1,b1<a2<b2等等）
所以就是对应排名的值要放在对应位置。这就是题目给的值两两不同的原因。离散化一下，题目转化为有两个1~n的排列，使它们对应位置的值相等，最少要交换多少次。
之前做过题，知道相邻交换一下可以使逆序对数减且仅减1。怎么转化？
考虑发现两行的操作完全是等价的。也就是一行的一个操作可以等价转换成另一行的一个操作。这样只用操作一行即可。
就想到可以以一行的值的位置为基准给另一行的值重新赋值，赋成这个值在第一行中的位置。这样问题就转化成第二行中有多少个逆序对。树状数组求解即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5,mod=99999997; int n,a[N],b[N],tp[N],ps[N],f[N],ans; int rdn() { int ret=0,fx=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') fx=-1; ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return ret*fx; } void upd(int &x){x-=(x>=mod?mod:0);} int query(int x) { int ret=0; for(;x;x-=(x&-x)) ret+=f[x],upd(ret); return ret; } void add(int x) { for(;x<=n;x+=(x&-x)) f[x]++; } int main() { n=rdn(); for(int i=1;i<=n;i++) a[i]=tp[i]=rdn(); sort(tp+1,tp+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(tp+1,tp+n+1,a[i])-tp; for(int i=1;i<=n;i++) b[i]=tp[i]=rdn(); sort(tp+1,tp+n+1); for(int i=1;i<=n;i++) b[i]=lower_bound(tp+1,tp+n+1,b[i])-tp,ps[b[i]]=i; for(int i=1;i<=n;i++) { ans+=query(n-ps[a[i]]+1); upd(ans); add(n-ps[a[i]]+1); } printf("%d ",ans); return 0; }