백준 17429 - 국제 메시 기구 (C++)

문제

• 문제 링크

  
   BOJ 17429 - 국제 메시 기구 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리가 주어진다.
$Q$개의 쿼리에 대해 그에 맞는 처리를 진행하자.

• 제한

TL : $3$ sec, ML : $1024$ MB




$1 ≤ N ≤ 500,000$

$1 ≤ Q ≤ 100,000$

모든 출력에 있어서 $2^{32}$로 나눈 나머지 값을 출력 한다.

알고리즘 분류

• 자료구조(data structures)
• 트리(trees)
• 세그먼트 트리(segment tree)
• 느리게 갱신되는 세그먼트 트리(lazy propagation)
• heavy-light 분할(heavy-light decomposition)
• 오일러 경로 테크닉(euler_tour_technique)

풀이

이 문제 를 풀어 보았는가 ?
이번 문제는 위 문제를 트리 위에서 진행하는 것이다.

한가지 출제자분의 배려(?)인지는 모르겠으나 출력에 있어서 항상 2^32로 나눈 나머지를 출력해야 한다는 것이다.
이 말은 즉슨 역으로 unsigned int 자료형을 사용해 오버 플로우가 발생하도록 놔두는 것이 정답이라는 것.

앞서 언급한 문제에서처럼 세그먼트 트리는 단순 합세그로 구성하며, lazy에서 두 개의 값을 관리하자.
각각 곱해지는 값, 더해지는 값에 해당하며 $lazy[i] = a * x + b$ 의 형태로 값을 관리해주면 된다.
이때 $lazy[]$ 의 기저 상태는 $1 * x + 0$ 로 잡아주는 것이 편하다.

---

우리는 선형 구조에서 위 문제를 풀 수 있었다.
이에 따라 트리에 선형적으로 접근할 수 있도록 hld 로 트리를 분할하자.
각 쿼리는 한 정점의 서브 트리에 날리는 경우 ( $1, 3, 5$ ) 와 동떨어진 두 정점 간 경로 쿼리 ( $2, 4, 6$ ) 로 나눠 볼 수 있다.

첫번째 경우

$X$의 서브 트리에만 업데이트가 적용되므로 $in[X]$ 부터 $out[X]$ 까지에 대해 업데이트 쿼리를 날리면 된다.

두번째 경우

정점 $X$부터 정점 $Y$로의 경로에 대해 업데이트가 적용되므로 $X, Y$가 같은 체인에 속할 때 까지 깊이가 낮은 체인부터 업데이트 쿼리를 날리며 끌어 올려준다.
이후 $Depth[X] < Depth[Y]$인 $X, Y$에 대해 최종 쿼리를 날리면 된다.

전체 코드

#include<bits/stdc++.h>
#define r int n, int s, int e
#define ll unsigned int
#define N 500001
using namespace std;
 
vector <int> Gr[N], G[N];
ll seg[1 << 20], lz[1 << 20][2];
int top[N], in[N], out[N];
int S[N], P[N], D[N];
int n, q, o, i, j, k;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n >> q; i < n - 1; i++)
        cin >> j >> k, Gr[j].push_back(k), Gr[k].push_back(j);
}
void HldDfs1(int p)
{
    S[p] = 1;
    for (int& i : Gr[p])
        if (!S[i])
        {
            D[i] = D[p] + 1;
            P[i] = p;
            HldDfs1(i);
            S[p] += S[i];
            G[p].push_back(i);
            if (S[i] > S[G[p][0]]) swap(G[p][0], G[p].back());
        }
}
void HldDfs2(int p)
{
    in[p] = ++o;
    for (int& i : G[p])
        top[i] = i == G[p][0] ? top[p] : i, HldDfs2(i);
    out[p] = o;
}
void LazyUpdate(r)
{
    if (lz[n][0] == 1 && !lz[n][1]) return;
    seg[n] *= lz[n][0];
    seg[n] += (e - s + 1) * lz[n][1];
    if (s ^ e)
    {
        lz[n << 1][0] *= lz[n][0], lz[n << 1][1] *= lz[n][0], lz[n << 1][1] += lz[n][1];
        lz[n << 1 | 1][0] *= lz[n][0], lz[n << 1 | 1][1] *= lz[n][0], lz[n << 1 | 1][1] += lz[n][1];
    }
    lz[n][0] = 1, lz[n][1] = 0;
}
ll SegUpdate(r, int p, int q, ll k, ll v)
{
    LazyUpdate(n, s, e);
    if (s > q || e < p) return seg[n];
    if (s >= p && e <= q)
    {
        lz[n][0] = k; lz[n][1] = v;
        return LazyUpdate(n, s, e), seg[n];
    }
    int m = (s + e) >> 1;
    return seg[n] = SegUpdate(n << 1, s, m, p, q, k, v) + SegUpdate(n << 1 | 1, m + 1, e, p, q, k, v);
}
ll SegQuery(r, int p, int q)
{
    LazyUpdate(n, s, e);
    if (s > q || e < p) return 0;
    if (s >= p && e <= q) return seg[n];
    int m = (s + e) >> 1;
    return SegQuery(n << 1, s, m, p, q) + SegQuery(n << 1 | 1, m + 1, e, p, q);
}
void HldUpdate(int p, int q, int k, int v)
{
    while (top[p] ^ top[q])
    {
        if (D[top[p]] < D[top[q]]) swap(p, q);
        SegUpdate(1, 1, n, in[top[p]], in[p], k, v);
        p = P[top[p]];
    }
    if (D[p] > D[q]) swap(p, q);
    SegUpdate(1, 1, n, in[p], in[q], k, v);
}
ll HldQuery(int p, int q, ll t = 0)
{
    while (top[p] ^ top[q])
    {
        if (D[top[p]] < D[top[q]]) swap(p, q);
        t += SegQuery(1, 1, n, in[top[p]], in[p]);
        p = P[top[p]];
    }
    if (D[p] > D[q]) swap(p, q);
    return t + SegQuery(1, 1, n, in[p], in[q]);
}
void Solve()
{
    while (q--)
    {
        cin >> o >> i;
        if (o == 1) cin >> j, SegUpdate(1, 1, n, in[i], out[i], 1, j);
        else if (o == 2) cin >> j >> k, HldUpdate(i, j, 1, k);
        else if (o == 3) cin >> j, SegUpdate(1, 1, n, in[i], out[i], j, 0);
        else if (o == 4) cin >> j >> k, HldUpdate(i, j, k, 0);
        else if (o == 5) cout << SegQuery(1, 1, n, in[i], out[i]) << '\n';
        else cin >> j, cout << HldQuery(i, j) << '\n';
    }
}
int main()
{
    Init();
    HldDfs1(1); HldDfs2(1);
    Solve();
}

comment

끝