백준 13519 - 트리와 쿼리 10 (C++)

문제

• 문제 링크

  
   BOJ 13519 - 트리와 쿼리 10 
  

• 문제 요약

금광 세그를 선형 구조가 아닌 트리 위에서 한다면?

• 제한

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




$2 ≤ N ≤ 100,000$

$1 ≤ Q ≤ 100,000$

$w_i ≤ |10,000|$

알고리즘 분류

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

풀이

여기 서 다룬 문제에서 이미 대차게 얻어 맞았었기 때문에 ,
사실상 복기하는 느낌으로 코드를 작성했다.
풀이는 저기서 다룬 내용과 99% 동일하니 간략하게 차이점만 짚고 넘어 가겠다.

그나마 차이점이라곤 $N$ 및 $Q$의 범위이며, 정답은 $0$보다 크거나 같다는 것이다.
이에 따라 레이지 값을 뿌려줄 때

$seg[n].ls = seg[n].rs = seg[n].ms =$ $max(lz[n], seg[n].ps)$ 가 아닌

$seg[n].ls = seg[n].rs = seg[n].ms =$ $max(0LL, seg[n].ps)$ 의 값을 취해 주는 것이 핵심이다.

위에서 언급한 문제가 답의 범위 제한이 없음에 따라, 좀 더 일반적인 형태인 듯 하다.

전체 코드

#include<bits/stdc++.h>
#define r ll n, ll s, ll e
#define ll long long
#define N 100001
using namespace std;
 
struct T { ll ls, rs, ps, ms; }seg[1 << 18];
vector <int> Gr[N], G[N];
int top[N], in[N], lz[1 << 18];
int P[N], D[N], S[N], C[N];
ll n, q, i, j, M(-1e9);
 
T f(T x, T y) { return { max(x.ls, x.ps + y.ls), max(y.rs, y.ps + x.rs), x.ps + y.ps, max({x.ms, y.ms, x.rs + y.ls}) }; }
void f0() // input
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    fill(lz, lz + (1 << 18), M); seg[n] = { M, M, 0, M };
    for (cin >> n; ++i <= n; cin >> C[i]);
    for (int o{}; o++ < n - 1;)
        cin >> i >> j, Gr[i].push_back(j), Gr[j].push_back(i);
}
void f1(int p)  // hld_init_dfs
{
    S[p] = 1;
    for (int& i : Gr[p])
        if (!S[i])
        {
            D[i] = D[p] + 1;
            P[i] = p;
            f1(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 f2(int p) // hld_init_dfs2
{
    in[p] = ++q;
    for (int& i : G[p])
        top[i] = i == G[p][0] ? top[p] : i, f2(i);
}
void f3(r) // lazy_update
{
    if (lz[n] == M) return;
    if (s ^ e) lz[n << 1] = lz[n << 1 | 1] = lz[n];
    seg[n].ps = lz[n] * (e - s + 1);
    seg[n].ls = seg[n].rs = seg[n].ms = max(0LL, seg[n].ps);
    lz[n] = M;
}
T f4(r, ll p, ll q, ll k) // seg_update
{
    f3(n, s, e);
    if (s > q || e < p) return seg[n];
    if (s >= p && e <= q) return (lz[n] = k, f3(n, s, e)), seg[n];
    T L(f4(n << 1, s, (s + e) >> 1, p, q, k)), R(f4(n << 1 | 1, ((s + e) >> 1) + 1, e, p, q, k));
    return seg[n] = f(L, R);
}
T f5(r, ll p, ll q) // seg_query
{
    f3(n, s, e);
    if (s > q || e < p) return seg[0];
    if (s >= p && e <= q) return seg[n];
    T L(f5(n << 1, s, (s + e) >> 1, p, q)), R(f5(n << 1 | 1, ((s + e) >> 1) + 1, e, p, q));
    return f(L, R);
}
void f6(ll x, ll y, ll w) // hld_update_query
{
    while (top[x] ^ top[y])
    {
        if (D[top[x]] < D[top[y]]) swap(x, y);
        f4(1, 1, n, in[top[x]], in[x], w);
        x = P[top[x]];
    }
    if (D[x] > D[y]) swap(x, y);
    f4(1, 1, n, in[x], in[y], w);
}
ll f7(ll x, ll y) // hld_get_query
{
    T p(seg[0]), q(seg[0]);
    while (top[x] ^ top[y])
        D[top[x]] > D[top[y]] ? p = f(f5(1, 1, n, in[top[x]], in[x]), p), x = P[top[x]] : (q = f(f5(1, 1, n, in[top[y]], in[y]), q), y = P[top[y]]);
    if (D[x] > D[y]) swap(x, y), swap(p, q);
    swap(p.ls, p.rs);
    return f(p, f(f5(1, 1, n, in[x], in[y]), q)).ms;
}
void sv()
{
    for (cin >> q, i = 1; i <= n; i++) f6(i, i, C[i]);
    for (ll o, w; q--;)
        if (cin >> o >> i >> j; o & 1) cout << f7(i, j) << '\n';
        else cin >> w, f6(i, j, w);
}
int main()
{
    f0();
    f1(1); f2(1);
    sv();
}

comment

끝