백준 26615 - 다오의 행사 계획하기 (C++)

문제

• 문제 링크

  
   BOJ 26615 - 다오의 행사 계획하기 
  

• 문제 요약

$N*M$ 크기의 미로 모양 행사장이 주어진다.
이곳에서 임의로 $K$개의 행사가 발생할 때, $T$일 간의 사람 수 변화를 구해보자.

• 제한

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




$ 2 ≤ N, M$

$N*M ≤ 10^5$

$1 ≤ T, K ≤ 10^9$

알고리즘 분류

• 트리(trees)
• 최소 공통 조상(lowest common ancestor)
• 누적 합(prefix_sum)

풀이

임의의 두 칸을 잇는 경로는 정확히 $1$개 있음이 보장된다고 한다. 즉, 미로는 트리이다.

두 칸을 잇는 경로에 대해 $V_i$명의 사람이 증가할 때, 영향 받는 칸의 수는 $LCA$ 및 $Sparse$ $Table$을 이용해 $O(logN)$만에 계산할 수 있다.

입력 처리 하는 게 살짝 귀찮긴 한데 어쨋거나 왼 쪽에서 오른 쪽으로, 위에서 아래로 증가 하도록 새로이 번호를 메겨 주는 것이 편하다.

---

$Q_i$ $:$ $S_i, E_i, a_i, b_i, c_i, d_i, V_i$ 에서

$x_i$ $:$ $p = (a_i, b_i), q = (c_i, d_i)$를 잇는 경로 위 등장하는 정점의 수

$x_i = $$Depth[p] + Depth[q] - 2 * Depth[LCA(p, q)] + 1$

로 간단하게 구할 수 있다.

쿼리는 전형적인 $imos$법의 형태로, $S_i$날에 $V_i*x*i$를 더해주고 $E_i + 1$날에 뺴준 후 스위핑 해주면 되겠다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 100001
using namespace std;
 
vector <int> Gr[N];
int D[N], dp[N][18];
ll n, m, t, S[N];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> t;
    for (int i{}; i < n - 1; i++)
        for (int j(1), o; j <= m; j++)
            if (cin >> o, !o)
            {
                int y(i * m + j), x(y + m);
                Gr[y].push_back(x), Gr[x].push_back(y);
            }
    for (int i{}; i < n; i++)
        for (int j(1), o; j < m; j++)
            if (cin >> o, !o)
            {
                int y(i * m + j), x(y + 1);
                Gr[y].push_back(x), Gr[x].push_back(y);
            }
}
void LCAInit1(int p, int q)
{
    D[p] = q;
    for (int& i : Gr[p])
        if (!D[i])
            dp[i][0] = p, LCAInit1(i, q + 1);
}
void LCAInit2()
{
    for (int j(1); j < 18; j++)
        for (int i(1); i <= n * m; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int GetLCA(int p, int q)
{
    if (D[p] < D[q]) swap(p, q);
    for (int i{}, d(D[p] - D[q]); d; d >>= 1, i++)
        if (d & 1)
            p = dp[p][i];
    if (p ^ q)
    {
        for (int i(17); i >= 0; i--)
            if (dp[p][i] ^ dp[q][i])
                p = dp[p][i], q = dp[q][i];
        p = dp[p][0];
    }
    return p;
}
void Solve()
{
    int q; cin >> q;
    for (ll s, e, i, j, y, x, v; q--;)
    {
        cin >> s >> e >> i >> j >> y >> x >> v;
        i = i * m + j + 1; j = y * m + x + 1;
        x = (D[i] + D[j] - 2 * D[GetLCA(i, j)] + 1) * v;
        S[s] += x, S[e + 1] -= x;
    }
    for (int i(1); i <= t; i++)
        S[i] += S[i - 1], cout << S[i] << '\n';
}
int main()
{
    Init();
    LCAInit1(1, 1);
    LCAInit2();
    Solve();
}

comment

끝