まず、求めなければならないコストの最小値は \(1\leq i<j\leq N\) かつ \(C_i\neq C_j\) かつ \(X_i>X_j\) であるような \((i,j)\) の個数に等しいです。

これについてはバブルソートにおいて必要な最低swap回数などと基本的に同じなので概略を述べるにとどめます。

以降では、左から \(i\) 番目の球と \(i+1\) 番目の球を入れ替える操作は \(X_i\)と\(X_{i+1}\), \(C_i\)と\(C_{i+1}\) を入れ替える操作に置き換えます。

コストの最小値を \(M\), 上記の条件をみたすペアの数を \(M'\) とします。球に書かれている数字が非減少な並び方においては \(M'=0\) であり、同色の隣接する球の入れ替えでは \(M'\) は減少せず、相異なる色の球の入れ替えでは\(1\) 回につき高々 \(1\) しか減少しないことから、\(M'\leq M\) であると言えます。 あとは、\(M'>0\) のとき何度かのコスト \(0\) のswapと\(1\)回の コスト \(1\) のswapで \(M'\)を減少させるようなswapができる事と\(M'=0\)のとき非減少な列に並べ替えられることを示せばよいです。ある状態において、まずコストを支払わずに、「連続する同じ色の球をブロックとしてみて、その中で昇順に並べ替える」事ができます。この作業が終わった後、\(1\leq i\leq N-1\) であって左から \(i\) 番目と \(i+1\) 番目の色が相異なるものをすべて確認し、もしすべてにおいて\(X_i\leq X_{i+1}\) ならば全体として非減少な列となっています。 そうでないとき、そのような \(i\) について入れ替えると、コスト \(1\) と引き換えに \(M'\) を必ず \(1\) 減らすことができます。 このことから、\(M'=M\) が従います。

さて、そのような \(i\) の求め方ですが、
\(1\leq i<j\leq N\) かつ \(X_i>X_j\) であるような \((i,j)\) の数を \(M_0\),
\(1\leq i<j\leq N\) かつ \(C_i=C_j=k\) かつ \(X_i>X_j\) であるような \((i,j)\) の数を \(M_k\) \((1\leq k\leq N)\)
として定めると、\(M'=M_0-\displaystyle\sum_{k=1}^N M_k\) となります。

これはただの反転数を求める問題であり, Fenwick木等によって, \(M_0\) は\(O(N\log N)\), \(M_k\) は \(O(N_k\log N_k)\) （ただし, \(N_k\) は\(C_i=k\) であるような球の数）で求める事ができます。

\(\displaystyle\sum_{k=1}^N N_k=N\) であることに注意すると, 必要な計算回数は適当な定数 \(C\) を用いて \(CN\log N+\displaystyle\sum_{k=1}^N CN_k\log N_k \leq CN\log N+\displaystyle\sum_{k=1}^N CN_k\log N =2CN\log N\) と計算でき, \(O(N\log N)\) で抑えられることが分かります。

よって、これらの値は十分高速に求める事ができ、この問題を解くことができました。

C++による実装例 :

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main() {
	int n, x, sz;
	int c[300000];
	vector<int>a[300001];
	long long ans = 0;

	cin >> n;
	for (int i = 0; i < n; i++)cin >> c[i];
	for (int i = 0; i < n; i++) {
		cin >> x;
		a[0].push_back(x - 1);
		a[c[i]].push_back(x - 1);
	}

	fenwick_tree<long long> fw(n);
	for (int i = 0; i <= n; i++) {
		sz = a[i].size();
		for (int j = 0; j < sz; j++) {
			if (i == 0)ans += fw.sum(a[i][j] + 1, n);
			else ans -= fw.sum(a[i][j] + 1, n);
			fw.add(a[i][j], 1LL);
		}
		for (int j = 0; j < sz; j++)fw.add(a[i][j], -1LL);
	}

	cout << ans << endl;
	return 0;
}