백준 16453 - Linhas de Metrô (C++)

문제

• 문제 링크

  
   BOJ 16453 - Linhas de Metrô 
  

• 문제 요약

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

• 제한

TL : $2$ sec, ML : $512$ MB




$5 ≤ N ≤ 100,000$

$1 ≤ Q ≤ 20,000$

알고리즘 분류

• 자료 구조(data structures)
• 트리(trees)
• heavy-light 분할(heavy-light decomposition)
• 세그먼트 트리(segment tree)
• 느리게 갱신되는 세그먼트 트리(lazy propagation)

풀이

쿼리 내용은 간단하다.
$Q : $ 트리 위 두 가지 경로가 주어질 때, 겹치는 정점의 수 ?

이는 $LCA$ $+$ $case$ $work$ 로 해결 하거나, 트리 위 경로 문제 답게 무지성 $HLD$ 를 박아서 해결 할 수 있다.

두 개의 경로 각각에 대해, 지나는 정점들마다 $1$을 업데이트 해준다면 $2$가 메겨진 정점들의 수가 곧 겹치는 정점의 수 아니겠는가 ?

구체적으로,
구간 단위 업데이트임에 따라 $lazy$ $propagation$ 을 적용한 뒤 합 쿼리를 뽑을 때 $seg[n] - (e - s + 1)$ 의 값을 취하자.
만약 $2$가 메겨진 정점이 없다면 자연스레 상쇄될 것이고, $2$가 메겨진 정점이 하나라도 있다면 그것들의 합을 모아준다는 것이다.

전체 코드

#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];
int D[N], P[N], S[N];
int seg[1 << 18], lz[1 << 18];
int n, q;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i, j, o{}; ++o < n;)
        cin >> i >> j, Gr[i].push_back(j), Gr[j].push_back(i);
}
void HldInit(int p)
{
    S[p] = 1;
    for (int& a : Gr[p])
        if (!S[a])
        {
            D[a] = D[p] + 1;
            P[a] = p;
            HldInit(a);
            S[p] += S[a];
            G[p].push_back(a);
            if (S[a] > S[G[p][0]]) swap(G[p][0], G[p].back());
        }
}
int o{};
void HldETT(int p)
{
    in[p] = ++o;
    for (int& a : G[p])
        top[a] = a == G[p][0] ? top[p] : a, HldETT(a);
}
void LazyUpdate(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] = 0;
}
int SegUpdate(r, int p, int q, int k)
{
    LazyUpdate(n, s, e);
    if (s > q || e < p) return seg[n];
    if (s >= p && e <= q)
    {
        lz[n] += k;
        return LazyUpdate(n, s, e), 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)
{
    LazyUpdate(n, s, e);
    if (s > q || e < p) return 0;
    if (s >= p && e <= q) return seg[n] - (e - s + 1);
    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)
{
    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);
        p = P[top[p]];
    }
    if (D[p] > D[q]) swap(p, q);
    SegUpdate(1, 1, n, in[p], in[q], k);
}
int HldQuery(int p, int q, 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]);
        p = P[top[p]];
    }
    if (D[p] > D[q]) swap(p, q);
    return x + SegQuery(1, 1, n, in[p], in[q]);
}
int main()
{
    Init(); HldInit(1); HldETT(1);
    for (int i, j, x, y; q--;)
    {
        cin >> i >> j >> x >> y;
        HldUpdate(i, j, 1); HldUpdate(x, y, 1);
        cout << HldQuery(x, y) << '\n';
        HldUpdate(x, y, -1); HldUpdate(i, j, -1);
    }
}

comment

끝