백준 25078 - Software Package Manager (C++)

문제

• 문제 링크

  
   BOJ 25078 - Software Package Manager 
  

• 문제 요약

$n$개의 정점으로 이루어진 트리와 $q$개의 쿼리가 주어진다.
각 쿼리를 알맞게 처리해보자.

• 제한

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




$7 ≤ n ≤ 100,000$

$5 ≤ q ≤ 100,000$

알고리즘 분류

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

풀이

여기 에서 다룬 문제의 하위호환 격인 문제다.

이 문제 역시 경로에 대한 구간 쿼리를 빠르게 처리해야 하므로 우선 hld로 트리를 분할하자.

각 쿼리에 대한 내용은 다음과 같이 정리할 수 있다.

• $install$ $x$ : 루트 정점부터 $x$까지 이르는 경로 상의 $uninstall$( $0$ )된 정점의 수 ?
• $uninstall$ $x$ : $x$를 루트로 하는 서브 트리 내 $install$( $1$ )된 정점의 수 ?

---

유효한 상태가 $0$ 또는 $1$ 로 표현되는 합 세그먼트 트리를 생각해보자. 또, 구간 단위로 업데이트 해야 하니 $Lazy$ $Propagation$ 을 적용하자.
그럼 각 쿼리에 대한 처리 방법을 정리해 볼 수 있다.

• $install$ $x$ : ( $Depth[x]$ ) $-$ ( $x$까지 이르는 경로 상의 구간 합 ) { 체인 단위로 처리해야 하므로 업데이트 역시 체인 단위로 진행해 주어야 한다. }
• $uninstall$ $x$ : $ETT$로 메겨진 $in[x]$과 $out[x]$의 구간 합을 통해 구할 수 있다. { 서브 트리 단위 이므로 한 번의 호출을 통해 업데이트를 마칠 수 있다. }

추가로 $0$ 역시 유효한 값으로 잡았기 때문에 $Lazy$ 에서의 기저 상태를 $-1$로 정의해 두었다.

전체 코드

#include<bits/stdc++.h>
#define r int n, int s, int e
#define N 100001
using namespace std;
vector <int> Gr[N], G[N];
int top[N], in[N], out[N];
int D[N], P[N], S[N];
int seg[1 << 18], lz[1 << 18];
int n, q, i, j;
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n; i < n - 1;)
        cin >> j, Gr[j].push_back(++i);
}
void HldDfs1(int p)
{
    S[p] = 1;
    for (int& a : Gr[p])
    {
        D[a] = D[p] + 1;
        P[a] = p;
        HldDfs1(a);
        S[p] += S[a];
        G[p].push_back(a);
        if (S[a] > S[G[p][0]]) swap(G[p][0], G[p].back());
    }
}
void HldDfs2(int p)
{
    in[p] = ++q;
    for (int& a : G[p])
        top[a] = a == G[p][0] ? top[p] : a, HldDfs2(a);
    out[p] = q;
}
void LazyProp(r)
{
    if (!!~lz[n])
        if (seg[n] = lz[n] * (e - s + 1); s ^ e)
            lz[n << 1] = lz[n], lz[n << 1 | 1] = lz[n];
    lz[n] = -1;
}
int SegUpdate(r, int p, int q, int k)
{
    LazyProp(n, s, e);
    if (s > q || e < p) return seg[n];
    if (s >= p && e <= q)
    {
        lz[n] = k;
        LazyProp(n, s, e);
        return seg[n];
    }
    int m = (s + e) >> 1;
    return seg[n] = SegUpdate(n << 1, s, m, p, q, k) + SegUpdate(n << 1 | 1, m + 1, e, p, q, k);
}
int SegQuery(r, int p, int q)
{
    LazyProp(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);
}
int HldQuery(int p, int q, int k, int x = 0)
{
    while (top[p] ^ top[q])
    {
        if (D[top[p]] < D[top[q]]) swap(p, q);
        x += SegQuery(1, 1, n, in[top[p]], in[p]);
        SegUpdate(1, 1, n, in[top[p]], in[p], k);
        p = P[top[p]];
    }
    if (D[p] > D[q]) swap(p, q);
    x += SegQuery(1, 1, n, in[p], in[q]);
    return SegUpdate(1, 1, n, in[p], in[q], k), x;
}
void Solve()
{
    cin >> q;
    for (string s; q--;)
    {
        cin >> s >> i;
        if (s == "install")
            cout << D[i] - HldQuery(0, i, 1) + 1 << '\n';
        else
            cout << SegQuery(1, 1, n, in[i], out[i]) << '\n', SegUpdate(1, 1, n, in[i], out[i], 0);
    }
}
int main()
{
    Init();
    HldDfs1(0);
    HldDfs2(0);
    Solve();
}

comment

끝