题目描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：
其中 ai 表示第一列火柴中第 i 个火柴的高度， bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入描述:

共三行，第一行包含一个整数 n ，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出描述:

一个整数，表示最少交换次数对 99,999,997 取模的结果。

示例1

输入
4
2 3 1 4
3 2 1 4
输出
1
说明
最小距离是 0 ，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

示例2

输入
4
1 3 4 2
1 7 2 4
输出
2
说明
最小距离是 10 ，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

备注

对于 10% 的数据， 1 ≤ n ≤ 10 ；
对于 30% 的数据， 1 ≤ n ≤ 100 ；
对于 60% 的数据， 1 ≤ n ≤ 1,000 ；
对于 100% 的数据， 1 ≤ n ≤ 100,000,0 ≤ 火柴高度 ≤ 231-1

解答


显然在两排中 每排第i小的分别对应就可取得最小值（对此不给予证明懒）

所以我们只在意两排的火柴是第几根 高度只需要用来进行排序（先把两个序列改成有序的方便离散化）

因此我们对火柴的高度进行离散化 把火柴高度变为1到n的序列

然后我们只需要对一个序列a固定 求另一个序列b相对于前一个序列a的逆序对即可

举个栗子😃：

a[]=1 123 7 966 1208; b[]=21 34 36 25 111;

离散之后得到：a[]=1 3 2 4 5;  b[]=1 3 4 2 5；

接下来是关键 对于每个a[i]的值对应一个i，b[i]映射到新序列的c[i]中 即c[a[i]]=b[i];（相当于以 a[i]为关键字对序列b[i]排序）

解释：即a中1在b中的位置为1 a中2在b中的位置为4 a中3在b中的位置为2 a中4在b中的位置为3 a中5在b中的位置为5

得到：c[]=1 4 3 2 5

最后求c的逆序对个数即可（用树状数组）

这里用到正序做树状数组求逆序对
正序做树状数组，那么当前下标减掉当前数字的前缀和即为以该数为较小数的逆序对个数。
因为是正序，那么对于每个当前的数，已加入的数字个数（算当前数）即为当前数字在数列中的下标，也就是树状数组中已经加入了这么多个数，那么他的前缀和代表小于它且在他前面的数的个数，用总数减掉前缀和即为以该数为较小数的逆序对个数，同样，我们也不需要考虑多算或少算的情况发生。
代码： 
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100010
#define mod 99999997
struct March
{
    int high;
    int order;//用来离散化
}a[maxn],b[maxn];
int n,ans;
int c[maxn],e[maxn];
bool cmp(March a,March b)
{
    return a.high<b.high;
}
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int t)
{
    while(x<=n)
    {
        e[x]+=t;
        e[x]%=mod;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int temp=0;
    while(x)
    {
        temp+=e[x];
        temp%=mod;
        x-=lowbit(x);
    }
    return temp;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].high;
        a[i].order=i;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i].high;
        b[i].order=i;
    }
    sort(1+a,1+a+n,cmp);
    sort(1+b,1+b+n,cmp);
    for(int i=1;i<=n;i++) c[a[i].order]=b[i].order;//关键
    for(int i=1;i<=n;i++)
    {
        add(c[i],1);//离散后的顺序就是正确的顺序
        ans+=i-sum(c[i]);//当前有几个元素减去之前比他大的数的个数 
        ans%=mod;
    }
    cout<<ans;
}



来源：Nanchtiy