BOJ 18874 - Haircut

BOJ 18874 - Haircut

Inverse Counting 를 세주는데, 좀 더 나아가서 수가 계속해서 제한될 때 변경해주며 세는 문제이다.

좀 헤맸는데, 뒤에서부터 줄여가면서 펜윅트리 두개로 다시 세는 방식으로 풀었다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);

   vvi idx(n + 1);
   vi v(n);
   vector<pi> c;
   for (int i = 0; i < n; i++) idx[a[i]].pb(i), c.pb({a[i], i});
   sort(all(c));
   int inv = 0;
   fenwick<int> fenw(n + 1), fenw2(n + 1);
   for (int i = 0; i < n; i++) {
      int cur = fenw.query(c[i].se, n);
      inv += cur;
      v[c[i].se] = cur;
      fenw.update(c[i].se, 1);
   }
   vi ans(n);
   for (int j: idx[n]) fenw2.update(j, 1);
   for (int i = n - 1; i >= 0; i--) {
      for (int j: idx[i]) {
         inv -= fenw2.query(0, j - 1);
      }
      for (int j: idx[i]) fenw2.update(j, 1);
      ans[i] = inv;
   }
   for (int i: ans) cout << i << endl;
}