BOJ 14458 - 소가 길을 건너간 이유 10

BOJ 14458 - 소가 길을 건너간 이유 10

Inversion Counting을 계속 원소들을 교체해가면서 세주는 문제이다.

여기서 처음 배열의 Inversion Counting을 세준다음에, 생각해보자.

제일 뒤의 원소를 제일 앞으로 보내는 연산은 다음과 같이 개수에 영향을 미친다.

$i$가 $to[i]$ 로 가야할 때, $n-1-to[i]$ 개 만큼 개수가 줄어든다.

왜냐면 $i$가 현재 가장 제일 마지막 원소이기 때문에 그것과 교차하는 것은 $n-1-to[i]$ 개의 $to[i]$ 오른쪽에 있는 원소들의 개수이기 때문이다.

또, $to[i]$ 만큼 교차하는 것의 개수가 늘어난다.

가장 앞으로 가면 그것과 교차하는 것의 개수는 $to[i]$개 가 증가하기 때문이다.

그러므로 이 연산을 쭉 해주면 된다.

주의할건, 처음 배열이 $A,B$ 가 주어졌을 때, $A$에서도 정답을 구해보고 $B$에서도 정답을 구해봐야 한다는 것이다.

struct fenwick {  
   vi tree;  
   int n;  
   fenwick(int n) : n(n), tree(vi(n + 1)) {}  
  
   void update(int i, int v) {  
      i++;  
      while (i <= n) {  
         tree[i] += v;  
         i += i & -i;  
      }  
   }  
   int sum(int i) {  
      i++;  
      int ret = 0;  
      while (i) {  
         ret += tree[i];  
         i -= i & -i;  
      }  
      return ret;  
   }  
};  
  
void solve() {  
   int n;  
   cin >> n;  
   vi a(n), c(n);  
   fv(a);  
   fv(c);  
   for (int &i: a) i--;  
   for (int &i: c) i--;  
   int A = 2e15;  
   for (int it = 0; it < 2; it++) {  
      auto b = c;  
      vi idx(n), to(n);  
      for (int i = 0; i < n; i++) idx[a[i]] = i;  
      for (int i = 0; i < n; i++) b[i] = idx[b[i]];  
      for (int i = 0; i < n; i++) to[b[i]] = i;  
  
      fenwick fenw(n);  
      ll inv = 0;  
      for (int i = n - 1; i >= 0; i--) {  
         inv += fenw.sum(to[i]);  
         fenw.update(to[i], 1);  
      }  
      ll ans = inv;  
      for (int i = n - 1; i >= 0; i--) {  
         inv += b[i] * 2ll - n + 1;  
         ans = min(ans, inv);  
      }  
      A = min(A, ans);  
      swap(a, c);  
   }  
   cout << A;  
}