백준 14287 - 회사 문화 3

참고

오일러 투어에 대해 모르면 여기를 먼저 보고 오자.

풀이

회사 문화 2와는 달리 더하는 방향이 반대이다. 어떻게 처리할 수 있을까? 일단 예제의 그래프를 그려보자.

 

 

여기서 정점 3에 3의 값을 더하면 1까지 3씩 더해야 한다. 하지만 단순히 간선 방향을 거꾸로만 하면 정점이 계속 중복 계산돼서 시간 초과 판정을 받고 방문 처리를 하면 사장까지 올라갈 수 없는 경로가 생겨 제대로 된 답을 계산할 수 없다.

 

이렇게 생각하면 무언가 떠올릴 수 있다.

 

부하의 칭찬을 나중에 한꺼번에 떠안자.

 

무슨 말이고 하면 정점 4에 5를 더하고 정점 2에 2를 더한 상태에서 정점 2의 칭찬도를 얻으려면 다음과 같이 할 수 있다.

 

 

아래로 값을 더하지 말고 2와 4의 값만 변경한 다음 2의 오일러 투어 구간 [2, 5]의 합을 구하면 7이 구해진다!

 

이런 방식으로 lazy propagation을 하지 않고도 단순히 일반 세그먼트 트리의 update와 sum 연산으로 쿼리마다 답을 구할 수 있게 된다.

 

전체 코드 - 여기서는 update 연산을 수행할 때 lazy propagation을 썼지만 update를 해도 문제없을 것이다.

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
vector<int> graph[100001];
int n, q;
 
template<typename T>
class lazy_segtree
{
public:
  vector<T> lazy, tree;
 
  lazy_segtree(int _n): lazy(_n * 4), tree(_n * 4)
  {
 
  }
 
  void prop(int node, int start, int end)
  {
    if (!lazy[node]) return;
    int range = end - start + 1;
    tree[node] += range * lazy[node];
    if (start != end)
    {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
 
  T sum(int node, int start, int end, int l, int r)
  {
    prop(node, start, end);
    if (start > r or end < l) return 0;
    if (l <= start and end <= r) return tree[node];
    int mid = start + (end - start) / 2;
    return sum(node * 2, start, mid, l, r) + sum(node * 2 + 1, mid + 1, end, l, r);
  }
 
  void add(int node, int start, int end, int l, int r, T val)
  {
    prop(node, start, end);
    if (start > r or end < l) return;
    if (l <= start and end <= r)
    {
      lazy[node] += val;
      prop(node, start, end);
      return;
    }
    int mid = start + (end - start) / 2;
    add(node * 2, start, mid, l, r, val);
    add(node * 2 + 1, mid + 1, end, l, r, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
  }
};
 
pii euler[100001];
int num;
void dfs(int cur, int par)
{
  euler[cur].first = ++num;
  for (int i : graph[cur])
  {
    if (i == par) continue;
    dfs(i, cur);
  }
  euler[cur].second = num;
}
 
void solve()
{
  cin >> n >> q;
  for (int i = 1; i <= n; i++)
  {
    int x;
    cin >> x;
    if (x == -1) continue;
    graph[x].push_back(i);
  }
 
  lazy_segtree<ll> tree(n);
  dfs(1, -1);
 
  while (q--)
  {
    int x, a, b;
    cin >> x;
    if (x == 1)
    {
      cin >> a >> b;
 
      int l = euler[a].first;
      tree.add(1, 1, n, l, l, b);
    }
    else
    {
      cin >> a;
      cout << tree.sum(1, 1, n, euler[a].first, euler[a].second) << '\n';
    }
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록