[NOIP2013 提高组] 《火柴排队》

P1966 解题报告

首先手玩一下样例，可以猜出这样一个贪心的结论：

a 中的每个数字都要对应 b 中相同 rank 的数字。

这个数据范围肯定先离散化的，在 rank 代表数字的离散化数组中，原 rank 相同就意味着离散化后的数字相同。于是上面的结论也可以写成：

离散化后的数组 a 一定与离散化后的数组 b 相等。

把一个数组 a 变换成另一个数组 b，实际上就是给数组 a 按照 b 定义一个新顺序，然后排序即可。

例如
a = {1, 3, 4, 2, 5}
b = {3, 2, 5, 4, 1}
令新顺序 n[b[i]] = i
n = {5, 2, 1, 4, 3}
n[i] 的意义就是 i 在 b 中的位置
然后按照新顺序重新获得 c[i] = n[a[i]]
c = {5, 1, 4, 2, 3}
c[i] 的意义就是 a[i] 在 b 中的位置，也就是按照 b 的顺序获得的新的 a[i]

交换两个相邻数字排成上升序列，这个很经典了，逆序对个数
直接树状数组或者归并即可。

代码实现

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <set>
#include <map>

const int MAXN = 100000 + 10;
const int HA = 1e8 - 3;

int n;
int fa[MAXN], fb[MAXN];
int aa[MAXN], bb[MAXN];
int neworder[MAXN];

// 基本原理是贪心，让 a 的所有元素都对应 b 的同排名元素
// 也就是离散化后让两个数组相等
// 定义新顺序后的逆序对数 

void lisan(int *a, int len, int *la) {
	static int ff[MAXN];
	for (int i = 1; i <= len; ++i) ff[i] = a[i];
	std::sort(a + 1, a + len + 1);
	for (int i = 1; i <= len; ++i) {
		la[i] = (int) (std::lower_bound(a + 1, a + len + 1, ff[i]) - a);
	}
	//printf("[DEBUG] la = {");
	//for (int i = 1; i <= len; ++i) 
	//	printf("%d%s", la[i], i == len ? "}
" : ", ");
}

void rearrange() {
	for (int i = 1; i <= n; ++i) neworder[bb[i]] = i;
	for (int i = 1; i <= n; ++i) fa[i] = neworder[aa[i]];
}

struct BIT {
	int ss[MAXN];
	
	#define lb(x) ((x) & (-(x)))
	
	BIT() {}
	void insert(int x) {
		for (; x <= n; x += lb(x)) (ss[x] += 1) %= HA;
	}
	int sum(int x) {
		int ret = 0;
		for (; x >= 1; x -= lb(x)) (ret += ss[x]) %= HA;
		return ret;
	}
} bit;

int solve() {
	int ans = 0;
	for (int i = n; i >= 1; --i) {
		(ans += bit.sum(fa[i])) %= HA;
		bit.insert(fa[i]);
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", fa + i);
	for (int i = 1; i <= n; ++i) scanf("%d", fb + i);
	lisan(fa, n, aa); lisan(fb, n, bb);
	rearrange();
	printf("%d
", solve());
	return 0;
}