Luogu P1966: [NOIP2013 提高组] 火柴排队 [树状数组+逆序对]

[NOIP2013 提高组] 火柴排队

题目描述

涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为： $\sum (a_i-b_i{)}^2$

其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。

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

输入格式

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

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

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

输出格式

一个整数，表示最少交换次数对 $10^8-3$ 取模的结果。

样例 #1

样例输入 #1

4
2 3 1 4
3 2 1 4

样例输出 #1

1

样例 #2

样例输入 #2

4
1 3 4 2
1 7 2 4

样例输出 #2

2

提示

【输入输出样例说明一】

最小距离是 $0$，最少需要交换 $1$ 次，比如：交换第 $1$ 列的前 $2$ 根火柴或者交换第 $2$ 列的前 $2$ 根火柴。

【输入输出样例说明二】

最小距离是 $10$，最少需要交换 $2$ 次，比如：交换第 $1$ 列的中间 $2$ 根火柴的位置，再交换第 $2$ 列中后 $2$ 根火柴的位置。

【数据范围】

对于 $10\%$ 的数据， $1\le n\le 10$；

对于 $30\%$ 的数据，$1\le n\le 100$；

对于 $60\%$ 的数据，$1\le n\le 10^3$；

对于 $100\%$ 的数据，$1\le n\le 10^5$，$0\le$ 火柴高度 $<2^{31}$。

思路

可以猜想出当两个数组中第$i$大的数字均相对应的时候，两个数组的距离最短。这个随便造两个例子就能大概证明结论是正确的。
然后我们就先使用离散化对数组进行处理，具体离散化的过程可以参考我这篇博客。
接下来的操作就非常精妙了，我们现在要解决的问题是，对于两个离散化后的数组$d_1$和$d_2$，其中一个数组通过几次相邻元素的交换之后可以得到另一个数组。下面我们通过新建一个数组$q$，令$q[d_1[i]]=d_2[i]$，得到的$q$数组就是以$d_1$为关键字，把$d_2$中的每个元素映射到$q$中。
那么我们的问题就转化成了求解$q$数组中逆序对的个数，这个和我上一篇博客解决的问题就几乎一样了。

代码

#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1e5+5;
const int mod = 1e8-3;
int a1[maxn], d1[maxn], a2[maxn], d2[maxn];
int c[maxn], q[maxn];
int n;

bool cmp1(int x, int y) {
    
    return a1[x]>a1[y];
}
bool cmp2(int x, int y) {
    
    return a2[x]>a2[y];
}

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

void add(int i) {
    
    while(i <= n) {
    
        c[i] = (c[i]+1)%mod;
        i += lowbit(i);
    }
}

int getsum(int i) {
    
    int res = 0;
    while(i > 0) {
    
        res = (res+c[i])%mod;
        i -= lowbit(i);
    }
    return res;
}

int main(void)
{
    
    freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
    
        scanf("%d", &a1[i]);
        d1[i] = i;
    }
    for(int i = 1; i <= n; ++i) {
    
        scanf("%d", &a2[i]);
        d2[i] = i;
    }
    sort(d1+1, d1+n+1, cmp1);
    sort(d2+1, d2+n+1, cmp2);
    for(int i = 1; i <= n; ++i) {
    
        q[d1[i]] = d2[i];
    }
    int ans = 0;
    for(int i = n; i >= 1; --i) {
    
        add(q[i]);
        ans = (ans+getsum(q[i]-1))%mod;
    }
    printf("%d\n", ans%mod);
    /* for(int i = n; i >= 1; ++i) { */
    /* printf("%d ", q[i]); */
    /* } */
    return 0;
}