**每次交换能且仅能消除一对**这个结论有没有问题？
by Edgebright @ 2023-07-07 14:50:16
我这样做是对的
AC code：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int mod=99999997;
struct innt{
int a;
int i;
}a[N],b[N];
int n,c[N],ans=0;
int t[N];
bool cmp(innt a,innt b){
return a.a<b.a;
}
int k[N];
void mergesort(int l,int r){
if(l==r)return;
int mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
int i=l,j=mid+1,cnt=l;
while(i<=mid&&j<=r){
if(c[i]<=c[j]){
k[cnt++]=c[i++];
}
else k[cnt++]=c[j++],ans+=mid-i+1,ans%=mod;
}
while(i<=mid)k[cnt++]=c[i++];
while(j<=r)k[cnt++]=c[j++];
for(int i=l;i<=r;i++)c[i]=k[i];
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].a;
a[i].i=i;
}
for(int i=1;i<=n;i++){
cin>>b[i].a;
b[i].i=i;
}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
for(int i=1;i<=n;i++){
t[a[i].i]=b[i].i;
}
for(int i=1;i<=n;i++){
c[i]=t[i];
// cout<<c[i]<<" ";
}
mergesort(1,n);
cout<<ans%mod;
return 0;
}
```
by Infinite_Progress @ 2023-07-19 19:15:14
@[xiangyike](/user/700106) 我知道了，我实现的时候直接用一个结构体存了一个位置的a和b，然后按a排序，以b为值算逆序对了。像我这样的话，相当于不仅是高度排名对应，还使a火柴有序了，这就必然导致最优性错误。你这样只是交换使排名对应，所以是正确的。
by Edgebright @ 2023-07-25 15:07:26
@[Edgebright](/user/762588) 我仔细一想好像还是不对，按a排序本身并没有增加交换次数，应该是排序后改变了b原本的顺序，貌似是正确性错误了（？
by Edgebright @ 2023-07-25 15:11:07
我感觉“$a_i<a_j$且$b_i > b_j$的火柴对数就是答案“这句话不太对。而应该是如果$a_i<a_j$且$b_i > b_j$，交换过去会更优，而交换的结果是ab高度排名相同的火柴处在同一位置。所以按题解那样按高度映射求逆序对才是正解（思维现在非常混乱
by Edgebright @ 2023-07-25 15:15:41