题解

把总共的逆序对数减去相同颜色的逆序对数

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a[300005], b[300005];
vector <int> bucket[300005];
long long merge(int *left, int *mid, int *right){
	vector <int> v(right - left + 1);
	int *i = left, *j = mid;
	int k = 0;
	long long ct = 0;
	while(i < mid && j < right){
		if(*i <= *j) v[k++] = *i++;
		else ct += mid - i, v[k++] = *j++;
	}
	while(i < mid) v[k++] = *i++;
	while(j < right) v[k++] = *j++;
	int len = right - left;
	for(int i = 0; i < len; i++){
		*left++ = v[i];
	}
	return ct;
}
long long get_inversion(int *left, int *right){//这项发明暂时还没申请专利，但是不准盗
	if(left + 1 >= right) return 0;
	int *mid = left + (right - left >> 1);
	return get_inversion(left, mid) + get_inversion(mid, right) + merge(left, mid, right);
}
int read(){
	char c = getchar();
	int x = 0, f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -f;
		c = getchar();
	}
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * f;
}
int main(){
	int n = read();
	for(int i = 1; i <= n; i++){
		b[i] = read();
	}
	for(int i = 1; i <= n; i++){
		a[i] = read();
		bucket[b[i]].push_back(a[i]);
	}
	long long ct = get_inversion(&a[1], &a[n + 1]);
	for(int i = 1; i <= n; i++){
		ct -= get_inversion(&bucket[i][0], &bucket[i][bucket[i].size()]);
	}
	cout << ct;

	return 0;
}