https://www.acmicpc.net/problem/1395


세그먼트 트리 lazy전파 유형입니다.

N만 작으면 비트마스크로 해결할 수 있을 것이라 생각했는데..

N도 너무 크고.. 흠.. 잘생각이 나지않았습니다.

스위치의 상태를 체크하려면 항상 그 범위만큼의 시간이 필요합니다.


하지만 lazy를 사용하면 해당 범위의 아래 부분은 나중에 업데이트를 하면 됩니다.

그리고 해당 범위의 노드에서 스위치 개수를 뒤집는 방법은

tree[node] = end - start + 1 - tree[node];

이용하면 됩니다.


범위의 개수에서 현재 on개수를 빼면 off개수가 나오기 때문이죠!


아래는 코드입니다.

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
#include <iostream>
#include <vector>
#include <cmath>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<int, int> vii;
typedef vector<ll, ll> vll;
 
 
void update_lazy(vi &tree, vi &lazy, int node, int start, int end) {
    if (lazy[node]) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        lazy[node] = 0;
    }
}
 
int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return tree[node];
    }
    else if (left <= start && end <= right) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int sum_query(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return 0;
    }
    else if (left <= start && end <= right) {
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return sum_query(tree, lazy, node * 2, start, mid, left, right) + sum_query(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    int tree_size = ceil(log2(n)) + 1;
    vi st(1 << tree_size);
    vi lazy(1 << tree_size);
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
 
        if (cmd) {
            cout << sum_query(st, lazy, 1, 1, n, a, b) << '\n';
        }
        else {
            update_range(st, lazy, 1, 1, n, a, b);
        }
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[12844] XOR  (0) 2017.08.26
[2517] 달리기  (0) 2017.08.16
[10999] 구간 합 구하기 2  (0) 2017.08.15
[2042] 구간 합 구하기  (0) 2017.08.15

https://www.acmicpc.net/problem/2263


헉헉..

엄청 어렵네요!!..


pre, in, post 각각의 순회는 이해했지만,

완벽히 이해한 것은 아니였나봅니다.


이 문제는

in과 post를 이용하여 pre를 유추하는 문제입니다.


post와 in의 특징을 제대로 이해하고 있다면

O(N)의 시간으로 해결할 수 있습니다.


우선 post에 특징에 대해서 말씀드리겠습니다.


post는 Left - Right - Root 순으로 순회를 합니다.

그렇다면 우리가 받는 post input에서 가장 끝이 트리의 root라는 것을 알 수 있습니다.


예제를 예로 들면 1 3 2 로 들어오니 2가 root라는 것을 알 수 있죠.


두번째로 in의 특징입니다.

in은 Left - Root - Right 순으로 순회를 합니다.

여기서 중요한 점!은 바로 in의 input을 그대로 받는 것이 아닌 그의 위치를 저장하는 것입니다.


예제를 예로 들면

1 2 3 이라는 input이 들어오니, pos[1] = 0, pos[2] = 1, pos[3] = 2

이런 식으로 위치를 저장합니다.

그 이유는


in을 사용해서 우리는 left, right 서브트리와 root로 구분을 지을 수 있기 때문입니다.


post를 이용하여 root를 찾았고, root가 무엇인지 안다면 in에서 그 root를 기준으로 left와 right 서브트리로 나눌 수 있습니다.


이러한 과정을 분할하면서 계속 반복한다면 원래의 트리 모양을 유추할 수 있겠지요.


pre는 Root - Left - Right 이므로 위의 특징들을 이용하여 root를 찾아낸 후 출력하고 in의 root를 기준으로

left서브트리의 노드 수와 right 서브트리의 노드 수를 체크하여 post트리에 적용한 후 그 노드 수를 기준으로 나눠주면 됩니다.



코드입니다.

pos배열을 선언할 때 배열의 개수가 MAX_SIZE + 1인 이유는 input이 1~N까지 들어오기 때문입니다.(이것 떄문에 엄청 틀렸습니다.)


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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int post[MAX_SIZE];
int pos[MAX_SIZE + 1];
 
void order(int is, int ie, int ps, int pe) {
    if (is > ie || ps > pe) return;
 
    int root = post[pe];
    cout << root << ' ';
 
    order(is, pos[root] - 1, ps, ps + pos[root] - is - 1);
    order(pos[root] + 1, ie, ps + pos[root] - is, pe - 1);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0, in; i < n; i++) {
        cin >> in;
        pos[in] = i;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> post[i];
    }
 
    order(0, n - 1, 0, n - 1);
 
    return 0;
}
 
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[C언어] 원형 큐(라운드 큐)  (0) 2017.09.07
[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13
이중 연결 리스트  (0) 2017.04.22

+ Recent posts

티스토리툴바