오일러 투어(Euler Tour) 응용 feat. 2820 자동차 공장

https://nicotina04.tistory.com/157

오일러 투어(Euler Tour) 기초

이 게시글에서는 전에 다루었던 오일러 투어를 응용하여 풀 수 있는 문제를 풀어본다.

 

https://www.acmicpc.net/problem/2820

2820번: 자동차 공장

 

트리 구조의 사내 관계에서 자기 부하의 월급을 변동시키는 쿼리가 주어진다.

 

특정 구간에 대해 값을 더하거나 빼는 것은 세그먼트 트리의 lazy propagation 또는 펜윅 트리로 수행할 수 있다.

 

다만 자신의 부하들을 어떻게 구간으로 표현할지 난감하다. 이는 오일러 투어로 해결할 수 있다.

 

오일러 투어 기초에서 보여준 3번째 구현법을 통해 트리를 재구성하자. 그러면 자신의 부하들을 구간으로 표현할 수 있게 된다.

 

오일러 투어로 재구축한 구간에 덧셈을 수행하면 월급의 변동을 손쉽게 처리할 수 있다. 다만 쿼리의 대상인 자기 자신은 월급을 변동하지 않는 것에 유의하며

 

닫힌 구간 [오일러 투어로 재구축한 자신의 노드 번호 + 1, 오일러 투어로 재구축한 자손 노드 중 마지막 노드 번호] 에 바뀐 월급을 반영하도록 한다.

 

이렇게 오일러 투어로 트리를 재구축하면 간단한 lazy propagation(혹은 펜윅 트리 응용) 문제로 바뀌게 된다.

 

다음은 이를 구현한 코드이다.

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, m;
int num;
int ar[500001];
int conv[500001];
int wage_conv[500001];
vector<int> tree[500001];
pii tour[500001];

inline int mid(int s, int e) { return s + (e - s) / 2; }

template<typename T>
class lazy_segtree
{
private:
  vector<T> tree, lazy;
public:
  lazy_segtree(int n): tree(n * 4), lazy(n * 4) { init(1, 1, n); }

  T init(int node, int start, int end)
  {
    if (start == end) return tree[node] = wage_conv[end];
    int m = mid(start, end);
    return tree[node] = init(node * 2, start, m) + init(node * 2 + 1, m + 1, end);
  }

  void propa(int node, int start, int end)
  {
    if (!lazy[node]) return;
    tree[node] += (end - start + 1) * lazy[node];

    if (start != end)
    {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }

    lazy[node] = 0;
  }

  void add(int node, int start, int end, int l, int r, T val)
  {
    propa(node, start, end);
    if (start > r || end < l) return;
    if (l <= start && end <= r)
    {
      lazy[node] += val;
      propa(node, start, end);
      return;
    }
    int m = mid(start, end);
    add(node * 2, start, m, l, r, val);
    add(node * 2 + 1, m + 1, end, l, r, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
  }

  T sum(int node, int start, int end, int l, int r)
  {
    propa(node, start, end);
    if (start > r || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int m = mid(start, end);
    return sum(node * 2, start, m, l, r) + sum(node * 2 + 1, m + 1, end, l, r);
  }
};

void dfs(int node)
{
  conv[node] = tour[node].first = ++num;

  for (int i: tree[node])
    dfs(i);

  tour[node].second = num;
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i)
  {
    cin >> ar[i];

    if (i == 1)
      continue;

    int par;
    cin >> par;
    tree[par].push_back(i);
  }

  dfs(1);

  for (int i = 1; i <= n; ++i)
    wage_conv[conv[i]] = ar[i];
  lazy_segtree<ll> segt(n);

  while (m--)
  {
    char inst;
    cin >> inst;
    if (inst == 'u')
    {
      int x;
      cin >> x;
      cout << segt.sum(1, 1, n, conv[x], conv[x]) << '\n';
    }
    else
    {
      int x, y;
      cin >> x >> y;

      if (tour[x].first == tour[x].second)
        continue;

      segt.add(1, 1, n, tour[x].first + 1, tour[x].second, y);
    }
  }
}

 

이 풀이를 배웠으면 주식회사 승범이네도 완전히 같은 방법으로 풀 수 있다. 다만 저 문제는 선택된 사원의 월급도 변동된다는 것에 유의하여 구간 덧셈을 수행하면 된다.

 

지금까지 오일러 투어를 응용하는 문제를 풀어보았다. 오일러 투어를 사용해야 되는 문제를 마주쳐도 막히지 않게 문제를 풀 수 있을 것이다!