문제링크 : 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 사용
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #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; } | cs |
문제유형
- 세그먼트 - 부모 자식 문제
- 트리가 편향되어있을때 O(NM)을 세그먼트에 넣어 O(NlgM)으로 만듬
- 세그먼트에 넣도록 노드를 배열에 각각 넣음
- l 배열 : 자기자신 인덱스, 다음값부터 자식 인덱스
- r 배열 : 자식 마지막 인덱스
- 업데이트 시 l+1 부터 r까지 업데이트
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 11066 파일 합치기 (0) | 2021.03.09 |
|---|---|
| 백준 10775 공항 (0) | 2021.03.09 |
| 백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP) (0) | 2021.03.04 |
| 백준 1865 웜홀 쉬운 풀이 (C++/CPP) (0) | 2021.03.04 |
| 백준 13549 숨바꼭질 3 (0) | 2021.03.03 |