80分求助
查看原帖
80分求助
755911
Ethereal_KQ楼主2023/12/23 12:17
#include<iostream>
using namespace std;
#define MAX 100000010
int n, res;
int pos[MAX], ans[MAX];
int a[MAX], b[MAX], c[MAX];
void MergeSort(int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	MergeSort(l, mid);
	MergeSort(mid + 1, r);
	int pa = l;
	int pb = mid + 1;
	int pc = l;
	while (pa <= mid and pb <= r) {
		if (ans[pa] <= ans[pb]) {
			c[pc++] = ans[pa++];
		} else {
			c[pc++] = ans[pb++];
			res += mid - pa + 1;
		}
	}
	while (pa <= mid) {
		c[pc++] = ans[pa++];
	}
	while (pb <= r) {
		c[pc++] = ans[pb++];
	}
	for (int i = l; i <= r; i++) {
		ans[i] = c[i];
	}
}
int nin = 99999997;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {

		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}
	for (int i = 1; i <= n; i++) {
		pos[a[i]] = i;
	}

	for (int i = 1; i <= n; i++) {
		ans[i] = pos[b[i]];
	}
	MergeSort(0, n);
	cout << res % nin << endl;
	return 0;
}
2023/12/23 12:17
加载中...