BOJ 16221 - 모독

BOJ 16221 - 모독

역시 플레 4~5 는 세그먼트 트리의 밭이다.

굉장히 많이나오고 사실 플레티넘 문제를 푼것같은 느낌이 안든다.

---

이 문제는 각 칸에 얼마나 수가 있는지를 추적하면서 하나도 없어졌을 때나 0에서 1이 되었을 때만 세그먼트 트리에 값을 업데이트 해주고 이분탐색으로 1부터 어디까지 이어져있는지 찾아주면 된다.

시간복잡도는 $O(N \log ^2N)$ 이다.

어디까지 이어져있는지 찾았다면 구해야하는건 결국 모든 개수의 합이므로 합을 관리하는 세그먼트 트리는 따로 관리해서 쿼리해주면 된다.

const int MAX = 1000000;  
void solve() {  
   int q;  
   cin >> q;  
  
   fenwick<int> fenw(MAX + 1), fenw_sum(MAX + 1);  
   vi cnt(MAX + 1);  
   cnt[0] = 1;  
   int last_ans = 0;  
   while (q--) {  
      int a, b;  
      cin >> a >> b;  
      if (a == 1) {  
         fenw_sum.update(b, 1);  
         cnt[b]++;  
         if (cnt[b] == 1) fenw.update(b, 1);  
      } else {  
         fenw_sum.update(b, -1);  
         cnt[b]--;  
         if (cnt[b] == 0) fenw.update(b, -1);  
      }  
      int l = 0, r = MAX, ret = 0;  
      while (l <= r) {  
         int m = l + r >> 1;  
         if (fenw.query(0, m) == m - 1 + 1) {  
            ret = m;  
            l = m + 1;  
         } else r = m - 1;  
      }  
      last_ans = ret;  
      cout << fenw_sum.query(1, ret) << endl;  
   }  
}