LzSeg 사용 시 주의 사항

배열 st와 lz를 이용하여 LzSeg를 구현한다고 가정하자.

st[p]에 접근하기 전에는 반드시 propagate(p, l, r)을 호출하여 lz의 데이터를 st에 반영해줘야 한다.

정말 기본적인 원칙인데 미처 생각하지 못하고 몇 시간 동안 디버깅하였다.

 

문제가 되었던 코드는 다음과 같다.

int ret = query(2 * p, l, m, i, j);

st[p] = max(st[2 * p], st[2 * p + 1]);

if (ret != -1)

    return ret;

ret = query(2 * p + 1, m + 1, r, i, j);

st[p] = max(st[2 * p], st[2 * p + 1]);

return ret;

 

query 함수 내에서 propagate 함수를 호출하고 있다.

(2 * p + 1)의 경우 query 함수를 호출하지 않았으므로 lz[2 * p + 1]의 데이터가 st[2 * p + 1]에 반영되지 않았을 수도 있다.

해결 방법은 문제마다 상이하므로 생략한다.

 

끝