BOJ 21814 - United Cows of Farmer John

BOJ 21814 - United Cows of Farmer John

$L_i$ 를 $b_i$와 동일한 값이 나오는 $i$보다 작은 인덱스 중 최대값이라 한다.

$[L_i+1, i-1]$ 의 구간에 $i$와 짝지어질 다른 리더의 후보가 존재한다.

그럼 여기서 $i$와 짝지어질 수 있으려면 구간에서 unique한 수의 개수를 세면 된다.

동일한 것이 여러개가 있다면 항상 제일 오른쪽 것만 또 다른 leader가 될 수 있기 때문이다.

이건 Merge sort tree나 Segment Tree로 세주면 된다.

가장 쉬운 방법은 Segment Tree로 $i$에서 $L_i$의 값을 $-1$ 해주고, $i$의 값을 $+1$ 해준다면 항상 특정 수의 가장 오른쪽 인덱스에만 트리의 값을 $+1$로 만들어둘 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   vi b(n);  
   fv(b);  
   vi val;  
   for (int i: b) val.pb(i);  
   uniq(val);  
   for (int &i: b) i = lbi(val, i);  
   int V = sz(val);  
   vvi idx(V, vi({-1}));  
   for (int i = 0; i < n; i++) idx[b[i]].pb(i);  
   for (int i = 0; i < V; i++) idx[i].pb(n);  
   vi L(n);  
   for (int i = 0; i < V; i++) {  
      for (int j: idx[i]) {  
         if (j == -1 || j == n) continue;  
         int I = lbi(idx[i], j);  
         L[j] = idx[i][I - 1];  
      }  
   }  
   int ans = 0;  
   fenwick<int> fenw(n + 1);  
   for (int r = 0; r < n; r++) {  
      int l = L[r];  
      ans += fenw.query(l + 1, r - 1);  
      fenw.update(r, 1);  
      if (~l) fenw.update(l, -1);  
   }  
  
   cout << ans;  
}