eff3ct's st0rage Dev Blog

[백준 BOJ] 17429. 국제 메시 기구

27 Jul 2022

난이도

Diamond IV

문제 풀이

끔찍한 길이의 HLD + 끔찍한 길이의 lazy prop 을 짜면 맞출 수 있는 문제다. 나는 코드길이가 8225byte(..)나 나왔다. 먼저, 오일러 투어 테크닉으로 서브트리에 대한 정보를 얻어두자. \(\scriptsize v\)를 루트로 하는 서브트리의 시작을 \(\scriptsize in[v]\)라고 하고, 끝을 \(\scriptsize out[v]\)라고 생각하자.

  • 1번 쿼리는 \(\scriptsize in[x]\)에서 \(\scriptsize out[x]\)까지 V를 더하면 된다. 다들 잘 알고 있는 구간에 값을 더하는 쿼리다.

  • 2번 쿼리는 경로에다가 값을 더하는 쿼리다. 이는 HLD로 해결해줄 수 있다. HLD로 해당 경로에다가 구간 값 업데이트 쿼리를 날려주면 된다.

3, 4번은 나중에 생각해보고 5, 6번을 먼저 보자.

  • 5번 쿼리는 \(\scriptsize in[x]\)에서 \(\scriptsize out[x]\)까지 구간 합 쿼리를 처리해 출력해주면 된다.

  • 6번 쿼리는 마찬가지로 HLD를 사용해 경로 위에서 값을 잘 얻어와줘서 출력하면 된다.

3, 4번 쿼리가 문제인데.. 얘네는 좀 복잡하다. 그냥 막 구간에 값을 곱한다고 바로 나오는게 아니라서 조금 생각을 해봐야 한다. \(\scriptsize (a, b)\)를 해당 노드에서 \(\scriptsize a\)만큼 곱하고 \(\scriptsize b\)만큼 더하는 lazy값이라고 생각해보자. 초기 lazy값은 다 \(\scriptsize (1, 0)\)이어야 함이 자명하다.

어떤 구간에 \(\scriptsize u\)가 곱해지고 \(\scriptsize v\)가 더해지는 쿼리가 들어왔다고 해보자. 그럼 \(\scriptsize (u, 0)\)이 되었다가 \(\scriptsize (u, v)\)가 되는게 자명하다. 그냥 그렇게 처리해주면 된다. 반면, 순서가 반대로 되면 조금 달라진다.

이번엔 반대로 어떤 구간에 \(\scriptsize v\)가 더해지고 \(\scriptsize u\)가 곱해지는 쿼리가 들어왔다고 해보자. 그러면, \(\scriptsize (1, v)\)가 되었다가 \(\scriptsize (u, uv)\)가 되어야 한다. 왜냐하면, 리프 노드값이 \(\scriptsize a\)라고 했을 때, \(\scriptsize a + v\) 에서 \(\scriptsize (a + v) \cdot u\)가 되기 때문이다. 즉, 더해지는 값이 uv가 된다. 그래서 합에 대한 레이지 값에도 \(\scriptsize u\)를 곱해줘야 하는 것이다.

흠.. 그러면 lazy를 어떻게 짜면 될까? 먼저 곱에 대한 propagate를 해주고 합에 대한 propagate를 해주면 된다. 그 이후 위의 내용을 적용시켜서 노드를 잘 업데이트 해주면 된다.

propagate_prod();
propagate_add();

//현재 노드 업데이트
//레이지 값 업데이트

느낌으로 짜주면 된다. 곱셈 update와 propagate에서는 합 lazy에 값을 곱하는 것을 잊지 않고 이리저리 잘 짜주면 된다. \(\scriptsize v\)를 곱하는 업데이트 함수를 짜라면 아래처럼 짜면 된다.

void update_product(int start, int end, int node, int left, int right, ll v) {
    propagate_prod(start, end, node);
    propagate_add(start, end, node);

    if(start > right || end < left) return;

    if(left <= start && end <= right) {
        tree[node] *= v;

        if(start != end) {
            lazy_prod[node * 2] *= v;
            lazy_prod[node * 2 + 1] *= v;
            lazy_add[node * 2] *= v;
            lazy_add[node * 2 + 1] *= v;
        }

        return;
    }

    int mid = (start + end) / 2;

    update_product(start, mid, node * 2, left, right, v);
    update_product(mid + 1, end, node * 2 + 1, left, right, v);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

요런 느낌이다.

흠.. 그럼 이제 레이지도 다 짰고, 각 쿼리에서 뭘 해야할 지 알았으니 그대로 구현을 해주면 된다. \(\scriptsize 2^{32}\)로 나눈 나머지를 구해야하기 때문에 나머지 연산을 잘 적용시켜서 풀면 된다.

.

.

.

.

.

.

라고 생각했지만, 그렇게 naive하게 풀면 정확하게 4퍼센트에서 WA를 받는다.

아마 보통 long long으로 세그먼트 트리의 노드를 관리할텐데 mod값이 너무 큰 나머지 곱해서 long long 범위를 초과할 수 있다. 헉! 무슨 뜬금없는 소리인가.. 그래서, 어떻게 해야하냐면 unsigned long long으로 모조리 고치던가 아니면, 그냥 unsigned int를 쓰는것으로 해결할 수 있다. 전자는 쉽게 이해가 갈꺼지만, 후자는 무슨 소리일까?

unsigned int에서 오버플로우가 나면 마치 \(\scriptsize 2^{32}\)로 mod값을 취한 효과가 발생한다. 헉.. 누가 이런 발상을 한대요? 진짜 무슨 생각으로 낸건지 궁금해진다. (아무리 생각해도 내 풀이가 맞아서 게시글을 봤는데 무려 이런 내용이;; ㅋㅋㅋㅋ __int128 써야할줄 알았는데 그건 아니였고 uint나 ull로 충분했다는 사실..) 그래서 mod값 처리할 필요없이 그냥 unsigned int로 다 처리해주면 AC를 받을 수 있다.

  • 1, 3, 5번 쿼리는 쿼리당 \(\scriptsize O(logN)\)이다. (세그 때문에)

  • 2, 4, 6번 쿼리는 체인들을 건너야 하니 \(\scriptsize O(logN)\)만큼의 시간이 더 들어 쿼리 당 \(\scriptsize O((logN)^{2})\)이다.

따라서, 총 시간복잡도 \(\scriptsize O(Q(logN)^{2})\)에 해결 가능하다.

uint가 너무 충격적인 문제였다.. hld + lazy부터 구현이 어질어질한데 ㅋㅋ mod 장난질도 한 대 얻어맞은 느낌.

코드 전문

17429 // 국제 메시 기구

Related posts