[NOIp2013] 火柴排队

题目

题目链接

题目大意：有两个长度为 $n$ 的序列 $a, b$，每次可以交换 $a, b$ 中相邻的两个数，最小化 $\sum(a_i - b_i)^2$。$1 \le n \le 10^5, 0 \le a_i, b_i \le 2^{31}$。

思路

首先有一个很明显的东西：$a$ 中第一大的应该跟 $b$ 中第一大的对应，$a$ 中第二大的应该跟 $b$ 中第二大的对应，以此类推。问题就转变为如何将 $b$ 的大小顺序变为 $a$ 的大小顺序。

先离散化一下。

之后相当于把 $b$ 变成 $a$，相当于按照 $a$ 的顺序对 $b$ 数组排序。

我们可以设 $c_{b_i} = a_i$，那么问题就变为了对 $c$ 冒泡排序的次数，求逆序对即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef long long LL;

const LL mod = 1e8 - 3;

LL A[100010], B[100010], a[100010], b[100010], c[100010], t[100010];
LL ans;
int n;

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

LL query(int x) {
    LL s = 0;
    while (x) {
        s += t[x];
        x -= lowbit(x);
    }
    return s;
}

void modify(int x, LL p) {
    while (x <= n) {
        t[x] += p;
        x += lowbit(x);
    }
    return ;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i)    read(A[i]), a[i] = i;
    for (int i = 1; i <= n; ++i)    read(B[i]), b[i] = i;
    std::sort(a + 1, a + n + 1, [](int a, int b) {
        return A[a] < A[b];
    } );
    std::sort(b + 1, b + n + 1, [](int a, int b) {
        return B[a] < B[b];
    } );
    for (int i = 1; i <= n; ++i)    c[b[i]] = a[i];
    for (int i = n; i >= 1; --i) {
        ans += query(c[i] - 1);
        modify(c[i], 1);
        ans %= mod;
    }
    printf("%lld\n", ans % mod);
    return 0;
}