BOJ 14898 - 서로 다른 수와 쿼리 2

BOJ 14898 - 서로 다른 수와 쿼리 2

아이디어를 떠올리는데 오래 걸렸다.

---

우선 문제가 Offline Query를 막아둔 것으로, Mo’s Algorithm 따위의 해법을 봉쇄해놨다.

Dynamic Segment Tree 를 써야 하는데, 일반적인 Segment Tree엔 $[l, r]$ 부터 서로다른 수의 개수를 세는것 따위를 날릴 수 없으므로 Persistent Segment Tree 를 사용해서 문제를 해결한다.

하지만 PST로도 어떻게 이 문제를 해결할지를 고민해보아야 한다.

0-1 Segment Tree 처럼 노드를 구성해도 ($[L, R]$구간에서 서로 다른 개수) - ($[1,L-1]$ 구간에서 서로 다른 개수)가 문제의 정답이 아니기 때문이다.

이 문제의 풀이법은 조금 생소한데,

$a[i]=x$ 라면 PST에서 $x$ 의 값을 $1$ 로 설정해주는 것이다.

$x$가 이전에 나왔다면 그부분에 대한 값은 $0$ 으로 되돌린 뒤 PST를 구성하자.

즉, $a$ 의 각 값에 대해 한 번 혹은 두 번 업데이트를 하는 것이다.

이제 PST에서 R 버전의 트리를 갖다가 $[L, \infty]=[L, R]$ 쪽의 합을 세주면 $L$ 이상의 인덱스에서 나온 수들은 PST에서 $1$을 갖고 있게 되므로 그 값을 세주면 끝이다.

메모리를 잘 최적화하도록하자…

struct Node { int l = -1, r = -1, v = 0; };  
struct PST {  
   vi version;  
   int N;  
   vector<Node> tree;  
  
   PST(int n) : N(n) {  
      tree.reserve(7000000);  
      tree.pb({});  
      version.pb(0);  
   }  
   int update(int i, int v) {  
      int prev_root = version.back();  
      int root = sz(tree);  
      tree.pb({}), version.pb(root);  
      update(prev_root, root, 0, N - 1, i, v);  
      return sz(version) - 1;  
   }  
   int query(int version_idx, int l, int r) {  
      return query(version[version_idx], 0, N - 1, l, r);  
   }  
private:  
   void update(int prev, int cur, int nl, int nr, int i, int v) {  
      if (cur == -1 || nr < i || nl > i) return;  
      if (nl == nr) {  
         tree[cur].v = v;  
         return;  
      }  
  
      int m = nl + (nr - nl) / 2;  
      if (i <= m) {  
         int new_child = sz(tree);  
         if (~prev) {  
            if (~tree[prev].r) tree[cur].r = tree[prev].r;  
            tree.pb(tree[prev].l != -1 ? tree[tree[prev].l] : Node());  
         } else tree.pb({});  
         tree[cur].l = new_child;  
         update(tree[prev].l, tree[cur].l, nl, m, i, v);  
      } else {  
         int new_child = sz(tree);  
         if (~prev) {  
            if (~tree[prev].l) tree[cur].l = tree[prev].l;  
            tree.pb(tree[prev].r != -1 ? tree[tree[prev].r] : Node());  
         } else tree.pb({});  
         tree[cur].r = new_child;  
         update(tree[prev].r, tree[cur].r, m + 1, nr, i, v);  
      }  
  
      tree[cur].v = (~tree[cur].l ? tree[tree[cur].l].v : 0) + (~tree[cur].r ? tree[tree[cur].r].v : 0);  
   }  
   int query(int n, int nl, int nr, int l, int r) {  
      if (n == -1 || nr < l || nl > r) return 0;  
      if (nl >= l && nr <= r) return tree[n].v;  
      int m = nl + (nr - nl) / 2;  
      return query(tree[n].l, nl, m, l, r) + query(tree[n].r, m + 1, nr, l, r);  
   }  
};  
  
void solve() {  
   int n, q;  
   cin >> n;  
   vi a(n), v;  
   fv(a);  
   v = a;  
   uniq(v);  
   for (int &i: a) i = lbi(v, i);  
   cin >> q;  
   PST pst(n + 5);  
   vi last_idx(sz(v), -1);  
   v.clear();  
   debug(sz(v));  
   v.resize(n + 1);  
  
   for (int i = 1; i <= n; i++) {  
      if (last_idx[a[i - 1]] != -1) {  
         pst.update(last_idx[a[i - 1]], 0);  
      }  
      v[i] = pst.update(i, 1);  
      last_idx[a[i - 1]] = i;  
   }  
  
   ll Q = 0;  
   while (q--) {  
      ll x, r;  
      cin >> x >> r;  
      ll l = x + Q;  
      Q = pst.query(v[r], l, r);  
      cout << Q << endl;  
   }  
}