백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/2820

아이디어

• 상사와의 관계를 인접 행렬로 관리

  • 업데이트 할경우 인접행렬을 업데이트
  • 시간복잡도 : O(M * N) : 2.5e11 > 시간초과

• 레이지 개념 사용할 수 있을까?

  • a의 부하의 월급을 증가할떄 : a에 임시로 달아놓음
  • u로 출력할때 : 상사에서부터 lazy 업데이트 후 출력
  • 시간복잡도 : 편향트리일때 O(MN) > 시간초과

• 자식 관계를 세그먼트 트리에 입력

  • 트리가 편향되어있을때 O(NM)을 세그먼트에 넣어 O(NlgM)으로 만듬
  • 세그먼트에 넣도록 노드를 배열에 각각 넣음
  • l 배열 : 자기자신 인덱스, 다음값부터 자식 인덱스
  • r 배열 : 자식 마지막 인덱스
  • 업데이트 시 l+1 부터 r까지 업데이트

시간복잡도 계산

• 세그먼트 트리 생성 : O(NlgN)
• 출력 : O(MlgN)

인트 계산

• 트리 : 항상 2^31-1 이하이지만 중간에 넘칠 수 있으므로 > ll 사용
• lazy :중간에 넘칠수 있으므로 ll 사용

코드

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
vector<ll> tree;
vector<ll> lazy;
 
int initSalary[500010];
int l[500010];
int r[500010];
int segToOrigin[500010];
vector<int> child[500010];
 
void dfs(int cur, int &idx) {
    l[cur] = ++idx;
    for(int x : child[cur]) dfs(x, idx);
    r[cur] = idx;
}
 
void make(int node, int st, int en) {
    if(st== en) {
        tree[node] = initSalary[segToOrigin[st]];
        return;
    }
    
    int mid = (st+en)/2;
    make(node*2, st, mid);
    make(node*2+1, mid+1, en);
}
 
void lazy_update(int node, int st, int en) {
    if(lazy[node] != 0) {
        if(st == en) tree[node] += lazy[node];
        else {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
void update(int node, int st, int en, int li, int ri, int diff) {
    lazy_update(node, st, en);
    if(ri < st || en < li) return;
    if(li <= st && en <= ri) {
        if(st == en) tree[node] += diff;
        else {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    
    int mid = (st+en)/2;
    update(node*2, st, mid, li, ri, diff);
    update(node*2+1, mid+1, en, li, ri, diff);
}
 
ll query(int node, int st, int en, int idx) {
    lazy_update(node, st, en);
    if(st == en) return tree[node];
    
    int mid = (st+en)/2;
    if(idx <= mid) return query(node*2, st, mid, idx);
    else return query(node*2+1, mid+1, en, idx);
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(initSalary, initSalary+500010, 0);
    fill(l, l+500010, 0);
    fill(r, r+500010, 0);
    fill(segToOrigin, segToOrigin+500010, 0);
    int N,M; cin >> N >> M;
    
    cin >> initSalary[1];
    
    for(int i=2; i<=N; i++) {
        int a,b; cin >> a >> b;
        initSalary[i] = a;
        child[b].push_back(i);
    }
    int idx = -1;
    // 세그먼트 위치 설정
    dfs(1, idx);
    
    // 세그먼트에서 원래로 가는 값
    for(int i=1; i<=N; i++) {
        segToOrigin[l[i]] = i;
    }
        
    int h = ceil(log2(N));
    tree.resize(1<<(h+1));
    lazy.resize(1<<(h+1));
    
    make(1,0,N-1);
    for(int i=0; i<M; i++) {
        char order; cin >> order;
        if(order == 'p') {
            int a,b; cin >> a >> b;
            // 자식이 없으면 건너뜀
            if(l[a] == r[a]) continue;
            update(1,0,N-1,l[a]+1, r[a], b);
        } else {
            int a; cin >> a;
            cout << query(1,0,N-1,l[a]) << '\n';
        }
    }
    
    return 0;
}
 

문제유형

• 세그먼트 - 부모 자식 문제
  • 트리가 편향되어있을때 O(NM)을 세그먼트에 넣어 O(NlgM)으로 만듬
  • 세그먼트에 넣도록 노드를 배열에 각각 넣음
  • l 배열 : 자기자신 인덱스, 다음값부터 자식 인덱스
  • r 배열 : 자식 마지막 인덱스
  • 업데이트 시 l+1 부터 r까지 업데이트