【原题】
题目描述
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$∑(ai−bi)^2 $
其中 ai 表示第一列火柴中第 i 个火柴的高度，bib_ibi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 (10^8-3) 取模的结果。
输入格式
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
输出格式
一个整数，表示最少交换次数对 (10^8−31) 取模的结果。
输入输出样例
输入 #1
4
2 3 1 4
3 2 1 4
输出 #1
1
输入 #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≤n≤10)；
对于 30% 的数据，(1≤n≤100)；
对于 60% 的数据，(1≤n≤10^3)；
对于 100% 的数据，(1≤n≤10^5)；，(0≤) 火柴高度 < (2^{31})。
【思路】
要使得火柴距离最小，每个位置的火柴长度在自己序列的排名应该相等。离散化处理出火柴在自己序列的排名。存下数组a每个排名的位置，对应到数组b中，逆序对个数即最小交换次数。（对应位置的思想和P1439一致，都是把a数组变为1, 2, 3......n再和b数组比对）
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl '
'
#define lson rt << 1
#define rson rt << 1 | 1
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;
const int maxn = 1e5 + 7;
const int maxm = 1e9 + 7;
const int mod = 1e8 - 3;
int n, m;
int a[maxn], b[maxn], tmp[maxn], c[maxn], d[maxn];
int tree[maxn * 4], lz[maxn * 4];
void add(int n, int index, int L, int R, int rt)
{
if (L == R)
{
tree[rt] += n;
return;
}
int mid = (L + R) / 2;
if (index <= mid) add(n, index, L, mid, lson);
else add(n, index, mid + 1, R, rson);
tree[rt] = tree[lson] + tree[rson];
}
void push_down(int rt, int l, int r) {
if (lz[rt]) {
int mid = (l + r) / 2;
lz[lson] += lz[rt];
lz[rson] += lz[rt];
tree[lson] += 1LL * (mid - l + 1) * lz[rt];
tree[rson] += 1LL * (r - mid) * lz[rt];
lz[rt] = 0;
}
}
void update_range(int rt, int l, int r, int L, int R, int add) {
if (l <= L && r >= R) {
lz[rt] += 1LL * add;
tree[rt] += 1LL * (R - L + 1) * add;
return;
}
push_down(rt, L, R);
int mid = (L + R) / 2;
if (mid >= l) update_range(lson, l, r, L, mid, add);
if (mid < r) update_range(rson, l, r, mid + 1, R, add);
tree[rt] = (tree[lson] + tree[rson]) % mod;
}
LL query_range(int rt, int l, int r, int L, int R) {
if (l <= L && r >= R) return tree[rt];
push_down(rt, L, R);
int mid = (L + R) / 2;
LL sum = 0;
if (mid >= l) sum = (sum + query_range(lson, l, r, L, mid)) % mod;
if (mid < r) sum = (sum + query_range(rson, l, r, mid + 1, R)) % mod;
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
_rep(i, 1, n)
{
cin >> a[i];
tmp[i] = a[i];
}
sort(tmp + 1, tmp + 1 + n);
_rep(i, 1, n)
{
a[i] = lower_bound(tmp + 1, tmp + n + 1, a[i]) - tmp;
c[a[i]] = i;
}
_rep(i, 1, n)
{
cin >> b[i];
tmp[i] = b[i];
}
sort(tmp + 1, tmp + 1 + n);
_rep(i, 1, n)
{
d[i] = lower_bound(tmp + 1, tmp + 1 + n, b[i]) - tmp;
d[i] = c[d[i]];
}
LL ans = 0;
_rep(i, 1, n)
{
ans = (ans + query_range(1, d[i], n, 1, n)) % mod;
add(1, d[i], 1, n, 1);
}
cout << ans << endl;
}