[BOJ] 24532번 : 트리와 XOR 쿼리

https://www.acmicpc.net/problem/24532

24532번: 트리와 XOR 쿼리

---

문제 요약

길지 않으니 직접 문제를 읽어보자.

---

풀이

하루정도 고민하다가 답 보고 해결했다. 에디토리얼이 정말 잘 되어있다. 

생각의 흐름을 요약해보자.

 

트리에서 어떤 두 정점 u, v의 단순 경로 상의 모든 가중치를 xor한 값을 d(u, v)라 하자.

어떻게 d(u, v)를  빠르게 구할까?

d(u, v) =  d(1, u) ^ d(1, v)를 이용하자. (xor 성질, 단순 경로)

 

정점 x의 서브 트리에 속한 임의의 정점 a, 정점 y의 서브 트리에 속한 임의의 정점 b에 대해서 모든 d(a, b)의 총합은 어떻게 구할까? (2번 쿼리)

xor연산을 다루는 중이므로 비트별로 쪼개서 생각해보자.

어떤 비트에 대해서

1. (d(1, a) = 1인 a의 개수) * (d(1, b) = 0인 b의 개수)

2. (d(1, a) = 0인 a의 개수) * (d(1, b) = 1인 b의 개수)

1.과 2.를 더한 후 비트에 해당하는 2의 거듭제곱을 곱한 값은 d(a, b)의 해당 비트만큼 기여한다. (xor 정의)

모든 비트에 대해서 더해주면 d(a, b)를 구할 수 있다.

 

따라서 우리는 d(1, a) = 0인 a의 개수, d(1, a) = 1인 a의 개수를 들고 있어야 한다.

위 두 개수의 합은 x의 서브 트리 크기와 같으므로 둘 중 하나만 들고 있어도 된다.

 

d(1, a) = 0인 a의 개수를 들고 다닌다고 해보자.

이를 오일러 투어 테크닉과 세그먼트  트리를 이용해 관리할 수 있다.

 

어떤 간선의 가중치가 변경되었을 때, 우리가 들고 있는 값들을 어떻게 변경해주어야 할까? (1번 쿼리)

정점 x와 그 부모 사이의 간선의 가중치가 변경되는 경우를 생각해보자.

해당 가중치 중 어떤 비트가 반전되면, 모든 d(1,  a)의 해당 비트도 반전된다.

 

세그먼트 트리에 어떤 서브 트리 내 비트를 반전하는 연산을 추가하자.

이는 lazy propagation으로 구현할 수 있다.

void update_lazy(ll x, ll s, ll e)
{
    if (lazy[x])
    {
        tree[x] = (e - s + 1) - tree[x];
        if (s != e)
        {
            lazy[x * 2] ^= 1;
            lazy[x * 2 + 1] ^= 1;
        }
        lazy[x] = 0;
    }
}
void update_range(ll x, ll s, ll e, ll l, ll r)
{
    update_lazy(x, s, e);
    if (l > e || s > r) return;
    if (l <= s && e <= r)
    {
        tree[x] = (e - s + 1) - tree[x];
        if (s != e)
        {
            lazy[x * 2] ^= 1;
            lazy[x * 2 + 1] ^= 1;
        }
    }
    else
    {
        update_range(x * 2, s, (s + e) / 2, l, r);
        update_range(x * 2 + 1, (s + e) / 2 + 1, e, l, r);
        tree[x] = tree[x * 2] + tree[x * 2 + 1];
    }
}

이거 구현하면서 꽤나 헤맸었는데, 해결하고 나니까 lazy propagation의 아이디어와 구현에 대한 이해가 더 깊어진 느낌이 든다.. 나중에 까먹지 않기를

---

느낀 점

• xor연산은 누적xor을 만들어 구간xor을 빠르게 처리할 수 있다.
• lazy propagation으로 처리할 수 있는 게 꽤나 다양한 것 같다.