BOJ 10070 - 벽

BOJ 10070 - 벽

어떻게 풀라는지 뻔히 알려주는 문제지만, Lazy Propagation Segment Tree를 정확히 이해하지 못하면 풀기가 까다롭다.

lazy 나 tree 같은 변수대신, mn와 mx 를 관리해준다.

$1$번 연산이 들어오면 자신의 mn, mx 를 모두 max 연산을 해주고 $2$번 연산은 모두 min 연산을 해준다.

이후에 자신에게 전파하는데, 두 자식 모두의 mn,mx 총 네개에 대해서 자신의 mn, mx 값을 적절히 전파해야 한다.

전파 후에 mn[n]=0 와 mx[n]=inf 를 해준다.

  void propagate(int n, int nl, int nr) {
      if (nl != nr) {
         int l = n * 2, r = n * 2 + 1;
         for (int c: {l, r}) {
            mn[c] = max(mn[c], mn[n]);
            mx[c] = max(mx[c], mn[n]);
            mn[c] = min(mn[c], mx[n]);
            mx[c] = min(mx[c], mx[n]);
         }
      }
      mn[n] = 0;
      mx[n] = 1e9;
   }