Made Up [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） C]

https://atcoder.jp/contests/abc202/tasks/abc202_c

解説

https://atcoder.jp/contests/abc202/submissions/22836846

ちょっとだけ整理

今回の問題は、解く前にまずは整理することが重要である。
B[C[j]]の部分であるが、別途配列Dを考えて、単純にD[j] = B[C[j]]として置き換えると、特に配列の配列として考える必要はなくなる。

全探索

これでi,jを全探索しようとすると10¹⁰通りくらいになるので間に合わない。
（全探索はできて10⁷くらいまで）
これをiだけ全探索してjは高速に求められる状態にしておくことで解決する。
とあるiを考えると対応するjはA[i]=D[j]であるjである。
よってA[i]=D[j]であるjの個数が前計算されていれば、高速に答えることができることになる。

cnt[x] = D[j]=xであるjの個数

この配列を前計算して作っておこう。
すると、とあるiのとき、条件を満たすjの個数はcnt[ A[i] ]となる。
これでACが取れる。

int N, A[101010], B[101010], C[101010], D[101010];
int cnt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    rep(i, 0, N) cin >> C[i];
    rep(j, 0, N) D[j] = B[C[j] - 1];

    rep(j, 0, N) cnt[D[j]]++;
    ll ans = 0;
    rep(i, 0, N) ans += cnt[A[i]];
    cout << ans << endl;
}