vijos1842(火柴排队)

描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：∑i=1n(ai−bi)2∑i=1n(ai−bi)2，其中 aiai 表示第一列火柴中第 i 个火柴的高度，bibi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

格式

输入格式

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

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

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

输出格式

输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

   样例输入：

4
2 3 1 4
3 2 1 4

样例输出

1

注意：同一列火柴高度互不相同。

定理：冒泡排序的的交换次数为数列的逆序数。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=100005;
const int MOD=99999997;
struct Node{
    int h,pos;
}a[MAXN],b[MAXN];
int n;
int bit[MAXN];
int c[MAXN];
bool comp(Node no1,Node no2)
{
    return no1.h < no2.h;
}
void add(int i,int x)
{
    while(i<MAXN)
    {
        bit[i]=(bit[i]+x)%MOD;
        i+=(i&-i);
    }
}
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        s=(s+bit[i])%MOD;
        i-=(i&-i);
    }
    return s;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i].h);
        a[i].pos=i+1;
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&b[i].h);
        b[i].pos=i+1;    
    }
    sort(a,a+n,comp);
    sort(b,b+n,comp);
    for(int i=0;i<n;i++)
    {
        c[a[i].pos-1]=b[i].pos;
    }
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=(res+i-sum(c[i]))%MOD;
        add(c[i],1);
    }
    printf("%d
",res);
    return 0;
}