BOJ 18798 - OR과 쿼리

image.png

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

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

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

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

이것의 알려진 보편적인 해답은 \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 연산은 무시되어도 된다.

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

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

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

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

Tags:

Categories:

Updated:

Comments