백준 11412 - Tree of Almost Clean Money (C++)

문제

• 문제 링크

  
   BOJ 11412 - Tree of Almost Clean Money 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리의 정보가 주어진다.
문제에 정의된 $x(i), y(i)$ 를 이용해 $Q$개의 쿼리에 대한 처리를 진행하자.

• 제한

TL : $4$ sec, ML : $256$ MB




$1 ≤ N ≤ 500,000$

$1 ≤ Q ≤ 50,000$

$1 ≤ K ≤ 1,000$

알고리즘 분류

• 자료 구조(data structures)
• 트리(trees)
• heavy-light 분할(heavy-light decomposition)
• 세그먼트 트리(segment tree)

풀이

이런 모양의 쿼리를 처음 접하기도 하고 영어 이슈 때문에 문제 이해 하는 게 제일 관건이었던 것 같다.
막상 문제를 이해하고 나면 별 게 없는 $HLD$ 기본 문제임을 알 수 있다.

이제 쿼리 내용을 보면, 총 $9$개의 변수가 주어진다. { $K, x(1), y(1), A, B, C, D, u, v$ }
또, 함수 $x(i)$와 $y(i)$는 다음과 같다.

$x(i) = (A * x(i - 1) + B)$ $mod$ $N$

$y(i) = (C * y(i - 1) + D)$ $mod$ $1,000,000,007$

여기에 변수 $K$ 는 $x(i), y(i)$의 호출 범위 및 그에 따른 업데이트 횟수를 뜻한다.
또 $x(1), y(1)$는 각각 $x(i), y(i)$의 기저값에 해당 되며 $A, B, C, D$는 $x(i), y(i)$의 식을 구성한다.

---

예제로 예를 들어 보면, 첫번째 쿼리의 $K$가 $1,000$임에 따라
$1 ≤ i ≤ 1000$ 의 범위에서

$x(1)$ 정점에 $y(1)$ 값 업데이트, $x(2)$ 정점에 $y(2)$ 값 업데이트, ... $x(1000)$ 정점에 $y(1000)$ 값 업데이트.
이런 식인 것이다.

이때 $i$가 순차적으로 증가함에 따라 매 순간마다 이전 호출의 결과를 이용하자.
즉, 각 호출의 결과를 임의의 변수에 누적 해주자.

이제 남은 건 정점 $u, y$를 잇는 경로 상에 합쿼리를 날려주는 일 뿐이다.

위를 구현함에 있어서 펜윅 트리를 이용 하는 것을 추천한다.
범위랑 제한 및 업데이트 쿼리 호출 횟수를 보면 재귀 세그로 $TLE$ 맞기 좋은 느낌이 든다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 500001
using namespace std;
 
vector <int> Gr[N], G[N];
int top[N], in[N];
int P[N], S[N], D[N], C[N];
ll n, q, xf, yf, Q[10], seg[N];
 
ll x(ll i) { return xf = i < 2 ? Q[2] : (Q[4] * xf + Q[5]) % n; }
ll y(ll i) { return yf = i < 2 ? Q[3] : (Q[6] * yf + Q[7]) % ((ll)1e9 + 7); }
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (ll i, j, o{}; ++o < n;)
    {
        cin >> i >> j; i++, j++;
        Gr[i].push_back(j), Gr[j].push_back(i);
    }
    for (ll i(1); i <= n; cin >> C[i++]);
}
void HldDfs(ll p)
{
    S[p] = 1;
    for (int& i : Gr[p])
        if (!S[i])
        {
            D[i] = D[p] + 1;
            P[i] = p;
            HldDfs(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 HldETT(int p)
{
    in[p] = ++q;
    for (int& i : G[p])
        top[i] = i == G[p][0] ? top[p] : i, HldETT(i);
}
void SegUpdate(ll p, ll q)
{
    while (p <= N - 1)
        seg[p] += q, p += p & -p;
}
ll SegQuery(ll p, ll r = 0)
{
    while (p)
        r += seg[p], p -= p & -p;
    return r;
}
ll HldQuery(ll p, ll q, ll r = 0)
{
    while (top[p] ^ top[q])
    {
        if (D[top[p]] < D[top[q]]) swap(p, q);
        r += (SegQuery(in[p]) - SegQuery(in[top[p]] - 1));
        p = P[top[p]];
    }
    if (D[p] > D[q]) swap(p, q);
    return r + SegQuery(in[q]) - SegQuery(in[p] - 1);
}
void Solve()
{
    for (ll i(1); i <= n; i++) SegUpdate(in[i], C[i]);
    for (cin >> q; q--; cout << HldQuery(Q[8] + 1, Q[9] + 1) << '\n')
    {
        for (ll i(1); i < 10; cin >> Q[i++]);
        for (ll i(1); i <= Q[1]; i++) SegUpdate(in[x(i) + 1], y(i));
    }
}
int main()
{
    Init();
    HldDfs(1); HldETT(1);
    Solve();
}

comment

끝