BOJ 18798 - OR과 쿼리

BOJ 18798 - OR과 쿼리

어제 코포 F가 이거랑 비슷한 문제라고 해서 공부해보았다.

$\lor$을 생각하지 말고 $\land$의 관점에서 접근하자.

어떤 수가 최대로 많이 바뀌는 횟수는 $0$에서 $2^{30}-1$ 까지 총 $30$번이다.

따라서 모든 수가 바뀌는 최대 횟수가 $O(30N)$ 임을 알 수 있고, 이걸 세그먼트 트리나 DSU를 이용해서 빠르게 업데이트 해주고 $K$가 될 때 펜윅 트리에 그 인덱스들을 저장해두는 방식으로 쿼리할 수 있다.

이것의 알려진 보편적인 해답은 $\land$를 저장하는 트리 노드들로 이루어지는 세그먼트 트리인것 같고, 구현은 다음과 같다.

struct SegTree {
   int N;
   vi tree;
   SegTree(int N) : N(N) {
      int size = 1 << int(ceil(log2(N) + 1));
      tree.resize(size);
   }

   void update(int n, int nl, int nr, int l, int r, int x) {
      if (nr < l || nl > r) return;
      if (nl >= 0 && nr <= 0 && (tree[n] & x) == x) return;
      if (nl == nr) {
         if (tree[n] == k) fenw.update(nl, -1);
         tree[n] |= x;
         if (tree[n] == k) fenw.update(nl, 1);
         return;
      }
      int mid = nl + nr >> 1;
      x &= ~tree[n];
      if (!x) return;
      update(n * 2, nl, mid, l, r, x);
      update(n * 2 + 1, mid + 1, nr, l, r, x);
      tree[n] = tree[n * 2] & tree[n * 2 + 1];
   }
};

노드가 의미하는 구간이 업데이트 하려는 구간 밖일때는 그냥 return 해줌은 동일하다.

특정 노드에 있는 모든 원소의 $\land$ 값이 업데이트하려는 값을 포함한다면 이 $\lor$ 연산은 무시되어도 된다.

따라서 만약 업데이트하려는 구간에 노드의 구간이 모두 포함되고 업데이트하려는 값$x$가 쓸모없다면 return 한다.

여기서 시간복잡도를 최적화하는 중요한 테크닉은 위의 19,20 번째 줄인데, 현재 구간의 $\land$ 값에서 $0$인 부분만 의미가 있으므로 $x$에서 그 부분만 남겨주고, $x=0$ 이 되었다면 더이상 propagation하지 않는 것이다.

이러한 형태의 세그먼트 트리는 처음봤고 시간복잡도도 헷갈렸지만 결국 $O(30N)$ 번만 업데이트가 된다는 것은 자명하다.

이런식으로 누적되는 연산들이 최대로 영향을 끼칠 수 있는 횟수의 상한을 파악해 문제를 해결하는 테크닉을 숙지해두도록 하자.