본문 바로가기

알고리즘 관련/BOJ

BOJ)2820 자동차 공장

문제: icpc.me/2820


문제를 잘 읽어보면 1번을 루트로 가지는 트리 구조를 이룬다는걸 알 수 있다.


그럼 상사 X의 부하들은 어떻게 구분할 수 있을까? 트리 구조이기 때문에 X에서 Y로 가는 경로는 오직 하나일 것이다. 이걸 이용하여 X지점에서 시작한 DFS가 끝날 때 까지 탐색되는 모든 노드들은 X의 부하라는걸 알 수 있다.


이를 이용하여 1번 노드에서부터 DFS를 돌려 정점의 번호를 새롭게 매겨준 후 DFS가 끝나는 지점(마지막 부하)의 번호까지 알게 된다면 직원에 대한 증가연산을 구간에 대한 증가 연산으로 치환시킬 수 있다,


구간에 대한 증가 연산으로 치환을 했으니 레이지 프로퍼게이션을 이용한 세그먼트 트리나 ,펜윅 트리 등을 이용하여 쿼리를 처리해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, c, s[500001], e[500001], lazy[2000000], seg[2000000], x, y, a[500001];
vector<vector<int>> vt;
char f;
void dfs(int here) {
    s[here] = ++c;
    for (auto next : vt[here])
        if (!s[next])
            dfs(next);
    e[here] = c;
}
void u_lazy(int node, int x, int y) {
    if (!lazy[node])
        return;
    seg[node] += lazy[node] * (y - x + 1);
    if (x != y) {
        lazy[node * 2+= lazy[node];
        lazy[node * + 1+= lazy[node];
    }
    lazy[node] = 0;
}
int update(int lo, int hi, int val, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)
        return seg[node];
    if (lo <= x&&<= hi) {
        lazy[node] += val;
        u_lazy(node, x, y);
        return seg[node];
    }
    int mid = (x + y) >> 1;
    return seg[node] = update(lo, hi, val, node * 2, x, mid) + update(lo, hi, val, node * + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&<= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    scanf("%d%d"&n, &m);
    vt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d"&a[i]);
        if (i != 1) {
            scanf("%d"&x);
            vt[x].push_back(i);
        }
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        update(s[i], s[i], a[i], 11, n);
    for (int i = 0; i < m; i++) {
        getchar();
        scanf("%c"&f);
        if (f == 'p') {
            scanf("%d%d"&x, &y);
            if (s[x] == e[x])continue;
            update(s[x] + 1, e[x], y, 11, n);
        }
        else {
            scanf("%d"&x);
            printf("%d\n", query(s[x], s[x], 11, n));
        }
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14502 연구소  (2) 2017.04.17
BOJ)3079 입국심사  (1) 2017.04.13
BOJ)7573 고기잡이  (0) 2017.04.12
BOJ)1202 보석 도둑  (0) 2017.04.12
BOJ)14499 주사위 굴리기  (2) 2017.04.12