离散化 树状数组

火柴排队

涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：

$∑i=(a_i−b_i)^2$
其中 $ai$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i_n$ 个火柴的高度。 

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离，最少需要交换多少次？

如果这个数字太大，请输出这个最小交换次数对 $99999997$ 取模的结果。

输入格式

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

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

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

输出格式

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

数据范围

$1\leq n\leq 10^5,0\leq 火柴高度\leq 2^31 − 1$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10,MOD = 99999997;

int a[N],b[N],c[N],p[N],tr[N];    //将a视为有序，c存储映射关系

int n;

//离散化

void disc(int a[]) {
    for(int i = 1; i <= n; ++ i) p[i] = i;
    sort(p + 1,p + n + 1,[&](int x,int y) {
        return a[x] < a[y];
    });
    for(int i = 1; i <= n; ++ i) a[p[i]] = i;
}

int lowbit(int x){
    return x & -x;
}

void add(int x,int val) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += val;
}

int query(int x){
    int res = 0;
    for(int i = x; i ; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; ++ i) scanf("%d",&a[i]);
    for(int i = 1; i <= n; ++ i) scanf("%d",&b[i]);
    for(int i = 1; i <= n; ++ i) cout << a[i] << " ";
        puts("");
    disc(a),disc(b);
    for(int i = 1; i <= n; ++ i) cout << a[i] << " ";
        puts("");
    for(int i = 1; i <= n; ++ i) c[a[i]] = i;
    int res = 0;
    for(int i = 1; i <= n; ++ i) {
        b[i] = c[b[i]];
        add(b[i],1);
        res  = (res + query(n) - query(b[i])) % MOD;
    }
    printf("%d",res);
    return 0;
}