[BOJ 15782]

문제 바로가기 : https://www.acmicpc.net/problem/15782
같은 유형, BOJ 12844 : https://www.acmicpc.net/problem/12844
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

review

상사-부하 간에 관계를 정리하기 위해 pre-order로 순회했습니다. 설명은 여기를 참고해주세요.
degurii님의 글을 참고했습니다. post-order로 구현하시고 싶으시면 참고하시길 권합니다.

XOR 연산을 홀수번하면 1번 한 것과 같고, 짝수번하면 안한 것과 같기 때문에 다음과 같이 조건을 걸었다.

void uplast_modified_at_lazy(int node, int start, int end) {
    if (lazy[node] != 0) {
        if ((end - start + 1) % 2) tree[node] ^= lazy[node]; //이 부분!
        if (start != end) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
        lazy[node] = 0;
    }
}

uplast_modified_at_range에서도 마찬가지이며, 기본적인 구조가 더하는 연산이라면 모두 XOR로 바꿔주면 된다.