[C++] 16404번 주식회사 승범이네 - 자료 구조, 그래프 이론, 트리, 세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 오일러 경로 테크닉

1. 문제

• 모든 판매원은 사수가 배정되며 한 회원당 단 한 명씩만 배정된다. 어떤 회원 A가 손해를 보면 그 회원의 모든 부사수도 같은 손해를 보고, 반대로 이익이 생기면 모든 부사수가 같은 이익을 본다. 승범이는 다음 두 종류의 명령을 처리하려 한다.
  • 1 i w : 작은 i가 w만큼 이익/손해를 본다.
  • 2 i : 직원 i의 현재 통장 잔액 출력
• 직원들은 빈 통장을 갖고 시작하며, 이익과 손해가 실시간으로 통장에 기록된다. 물론 통장 잔액은 음수일 수도 있다.

<입력>

• -1-   판매원의 수 $N(1\le N\le 100,000)$, 명령의 수 $M(1\le M\le 100,000)$
  • 판매원들은 1~N번호로 매겨지며 승범이는 항상 1이다.
• -2-   1~N 사수가 순서대로 주어진다. 승범이는 사수가 없으므로 -1이다.
• -M개-   명령 $(i,w\in \mathbb{Z},1\le i\le N,-100,000\le w\le 10,000)$

<출력>

• 2번 명령이 주어질 때마다 한 줄에 하나씩 해당하는 직원 i의 잔고 상황을 출력한다.

2. 재정의

• 자식이 하나밖에 없는 트리에서(부모 노드 제외)  한 노드와 그 모든 자식 노드의 값을 변화시킬 때 어느 노드의 값을 출력하라.

3. 해결 방법

• adj[a].push_back(b)로 그래프 완성
• dfs로 그래프를 탐색할 때 번호를 매기고 이 번호로 제일 처음 번호와 끝 번을 se<pair<int, int>>에 저장
• 느리게 갱신되는 세그먼트 트리를 수행

4. 실수한 점, 개선할 점

• dfs로 탐색한 번호를 dfs_num에 메모했는데 node랑 dfs_num이랑 햇갈려서 실수를 많이 했다.
• 팬윅 트리를 쓰면 시간이 단축되는 것 같은데... 뭐 얼마 단축 안되니까 상관없겠지?

 

<코드>

#include <iostream>
#include <cmath>
#include <vector>

#define pii pair<int, int>
#define Fi first
#define Se second

using namespace std;
typedef long long ll;

const int MAX_N = 100001;
const int MAX_Node = 1 << ((int)ceil(log2(MAX_N))+1);

// <문제>
// 판매원의 수, 명령의 수
int N, M;

// <그래프>
// 판매원 그래프
vector<int> adj[MAX_N];
// dfs로 탐색했을 때 번호와 시작과 끝
int dfs_num[MAX_N];
vector<pii> se(MAX_N);
int dfs_cnt;

// <Segment Tree Lazy Propagation>
ll tree[MAX_Node], lazy[MAX_Node];

void update_lazy(int node, int start, int end) {
    if(lazy[node]) {
        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 update_range(int node, int start, int end, int left, int right, ll diff) {
    update_lazy(node, start, end);
    if(end < left || right < start)
        return;
    if(left <= start && end <= right) {
        tree[node] += (end-start+1)*diff;
        if(end != start) {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    update_range(node*2, start, (start+end)/2, left, right, diff);
    update_range(node*2+1, (start+end)/2+1, end, left, right, diff);
    tree[node] = tree[node*2] + tree[node*2+1];
}

ll query(int node, int start, int end, int left, int right) {
    update_lazy(node, start, end);
    if(end < left || right < start)
        return 0;
    if(left <= start && end <= right)
        return tree[node];
    ll lsum = query(node*2, start, (start+end)/2, left, right);
    ll rsum = query(node*2+1, (start+end)/2+1, end, left, right);
    return lsum + rsum;
}

int dfs(int node) {
    // dfs 번호 매기기
    dfs_num[node] = ++dfs_cnt;
    
    int last = dfs_num[node];
    // 반환한 끝 번호 값을 last에 저장
    for(int i=0; i<adj[node].size(); i++)
        last = dfs(adj[node][i]);
    
    // 시작과 끝 저장
    se[node] = {dfs_num[node], last};
    
    return last;
}

void input() {
    cin >> N >> M;
    // 그래프 만들기
    for(int i=1; i<=N; i++) {
        int node;
        cin >> node;
        adj[node].push_back(i);
    }
    
    // dfs로 번호 매기기, 시작과 끝 찾기
    dfs(1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    for(int i=0; i<M; i++) {
        int what;
        cin >> what;
        
        if(what == 1) {
            int a, w;
            cin >> a >> w;
            update_range(1, 0, N-1, se[a].Fi-1, se[a].Se-1, w);
        }
        else {
            int a;
            cin >> a;
            cout << query(1, 0, N-1, dfs_num[a]-1, dfs_num[a]-1) << '\n';
        }
    }
    
    return 0;
}

 

 

<오일러 경로 테크닉(Euler Tour Technique)>

https://david0506.tistory.com/55

오일러 경로 테크닉(Euler Tour Technique)

 

<ceil() 함수>

https://blockdmask.tistory.com/112

[C언어/C++] 올림, 내림, 반올림 (floor, ceil) 함수

 

<느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)>

https://book.acmicpc.net/ds/segment-tree-lazy-propagation

느리게 갱신되는 세그먼트 트리

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.