BOJ 4442 - 빌보의 생일

BOJ 4442 - 빌보의 생일

Inversion Counting 으로 세면 된다.

void solve() {  
   while (1) {  
      int n;  
      cin >> n;  
      if (!n) break;  
      vs a(n), b(n);  
      fv(a);  
      fv(b);  
  
      map<string, int> a_idx;  
      vi to(n);  
  
      for (int i = 0; i < n; i++) a_idx[a[i]] = i;  
      for (int i = 0; i < n; i++) to[a_idx[b[i]]] = i;  
  
      vi tree(n + 1);  
      ll ans = 0;  
      for (int i = n - 1; i >= 0; i--) {  
         int j = to[i] + 1;  
         while (j) {  
            ans += tree[j];  
            j -= j & -j;  
         }  
  
         j = to[i] + 1;  
         while (j <= n) {  
            tree[j]++;  
            j += j & -j;  
         }  
      }  
      cout << ans << endl;  
   }  
}