BOJ 23245 - Similarity

BOJ 23245 - Similarity

헷갈렸지만 결국 pair로 된 길이 3의 LIS를 세는 문제였다.

$x[i]=(p_i,\,q_i)$ 라고 할 때, $x[i]<x[j]$ 인 조건은

$$ p_i < p_j~ \& ~q_i < q_j $$

이 조건을 처리해주기에 유의할 점은 $p_i$ 로 정렬을 한다음에 같은 $p_i$ 가 이전에 업데이트한 값들에 영향을 받지 않도록 잘 처리해주어야 한다는 것이다.

같은 $p_i$ 를 같는 인덱스들을 모두 묶어서 먼저 쿼리를 모두 날린다음에 그 다음 업데이트를 한 번에 해주고 다음 $p$ 로 넘어간다.

struct fenwick {  
   ...
};  
  
void solve() {  
   int n;  
   cin >> n;  
   vector<pi> p(n);  
   vi a(n), b(n);  
   fv(a);  
   fv(b);  
   for (int i = 0; i < n; i++) p[i].fi = a[i];  
   for (int i = 0; i < n; i++) p[i].se = b[i];  
  
   vi v;  
   for (int i: a) v.pb(i);  
   for (int i: b) v.pb(i);  
   uniq(v);  
   for (auto&[a, b]: p) a = lbi(v, a), b = lbi(v, b);  
   int V = sz(v);  
  
   fenwick fenw1(V), fenw2(V);  
   sort(all(p));  
  
   int ans = 0;  
   for (int i = 0; i < n; i++) {  
      int j = i;  
      while (j < n && p[i].fi == p[j].fi)j++;  
      j--;  
  
      vi ret1_pending;  
      for (int k = i; k <= j; k++) {  
         int ret = fenw1.q(0, p[k].se - 1);  
         ret1_pending.pb(ret);  
         ans += fenw2.q(0, p[k].se - 1);  
      }  
  
      for (int k = i; k <= j; k++) {  
         fenw1.upd(p[k].se, 1);  
         fenw2.upd(p[k].se, ret1_pending[k - i]);  
      }  
      i = j;  
   }  
   cout << ans;  
}