공장

쌍이 될 수 있는 전선은 내 앞의 인덱스들이 가지고 있는 전선만큼이다. 

#include <iostream>
#include <vector>
#define MAXX 500001
#define MAXXX 1000001
using namespace std;
 
typedef long long ll;
 
int n;
int num[MAXXX], arr[MAXX], tree[MAXX];
 
void update(int idx, int diff) {
    while(idx <= n) {
        tree[idx] += diff;
        idx += (idx & -idx);
    }
}
 
ll sum(int idx) {
 
    ll ret = 0;
    while(idx > 0) 
    {
        ret += tree[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 1; i<=n; i++) {
        int tmp;
        cin >> tmp;
        num[tmp] = i; //인덱스 저장
    }
 
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        arr[i] = num[tmp]; //인덱스만 저장 
    }
 
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        update(arr[i], 1); //내 앞에 위치한 점선들의 개수는 쌍이 된다. 
 
        ll res = sum(arr[i]);
        ans += (i-res);
    }
    cout << ans << '\n';
    return 0;
}