반응형

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

 

13537번: 수열과 쿼리 1

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/462

 

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)

1. 머지 소트 트리(Merge Sort Tree) 머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다. 2. 머지 소트 트리(Merge Sort Tree) 동작 원리 머지 소트 트리(Me

rudalsd.tistory.com

 

1. 수열을 입력받고, 머지 소트 트리를 구현합니다.

 

2. 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

3. 쿼리마다 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
 
void merge(int node, int s, int e) {
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0;
    int j = 0;
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i == s_size) {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
    else {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}
 
void getTree(int node, int s, int e, int i, int j, int k)
{
    if (e < i || j < s) return;
    if (i <= s && e <= j) {
        ans += mergeSortTree[node].end() - upper_bound(mergeSortTree[node].begin(), mergeSortTree[node].end(), k);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, i, j, k);
    getTree(node * 2 + 1, m + 1, e, i, j, k);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    cin >> M;
 
    for (int a = 0; a < M; a++) {
        int i, j, k;
        cin >> i >> j >> k;
        ans = 0;
 
        getTree(1, 1, N, i, j, k);
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
반응형

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

 

14463번: 소가 길을 건너간 이유 9

첫 줄에 N (1 ≤ N ≤ 50,000)이 주어진다. 다음 2N줄에는 한 줄에 하나씩 길 위의 점을 지나간 소의 번호가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. visited 배열을 선언하고, 소가 나오면 해당 위치를 visited 배열에 저장하고, 해당 위치의 Segment Tree 노드에 1을 더해줍니다.

 

2. 만약 입력받은 수가 이미 방문을 했다면 visited[ n ] + 1 ~ i - 1 까지의 구간합을 ans에 더해주고, visited[ n ]의 Segment Tree 노드에 -1을 해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int visited[50001];
int segTree[200000];
 
void updateTree(int idx, int diff)
{
    while (idx != 0) {
        segTree[idx] += diff;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
 
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    int ans = 0;
 
    for (int i = 1; i <= 2 * N; i++) {
        int a;
        scanf("%d", &a);
 
        if (visited[a] == 0) {
            visited[a] = i;
            updateTree(2 * N + i - 1, 1);
        }
        else {
            ans += getTree(2 * N + visited[a], 2 * N + i - 2);
            updateTree(2 * N + visited[a] - 1, -1);
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
[ 백준 ] 12919번 - A와 B 2 (C++)  (0) 2023.06.12
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
반응형

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

 

5817번: 고통받는 난쟁이들

옛날 옛적, 일곱 언덕과 일곱 바다를 건너 작은 마을이 있었어요. 백설공주는 놀고 먹고 자다가 일어나서 문명 5, 리그 오브 레전드, 풋볼 매니저를 하다가 다시 자는 난쟁이들 N명과 살고 있었어

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 난쟁이들의 키를 입력 받고, 난쟁이들의 키를 인덱스로, 난쟁이들의 위치를 값으로하는 세그먼트 트리를 만듭니다.

 

2. 각 노드에는 구간의 최댓값과 최솟값을 각각 저장합니다.

 

3. 해당 구간의 최댓값과 최솟값의 차이가 Y - X와 같다면 YES를 아니라면 NO를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
pair<int,int> segTree[524444];
int arr[200000];
int Min, Max;
 
void updateTree(int node, int s, int e, int idx, int n)
{
    if (idx < s || e < idx) return;
    if (s == e) {
        segTree[node] = { n, n };
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, idx, n);
    updateTree(node * 2 + 1, m + 1, e, idx, n);
 
    segTree[node].first = max(segTree[node * 2].first, segTree[node * 2 + 1].first);
    segTree[node].second = min(segTree[node * 2].second, segTree[node * 2 + 1].second);
}
 
void getTree(int node, int s, int e, int sidx, int eidx)
{
    if (e < sidx || s > eidx) return;
    if (sidx <= s && e <= eidx) {
        Min = min(Min, segTree[node].second);
        Max = max(Max, segTree[node].first);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, sidx, eidx);
    getTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
        updateTree(1, 1, N, arr[i], i);
    }
 
    for (int i = 0; i < M; i++) {
        int cmd, X, Y;
        scanf("%d %d %d", &cmd, &X, &Y);
 
        if (cmd == 1) {
            updateTree(1, 1, N, arr[Y], X);
            updateTree(1, 1, N, arr[X], Y);
            swap(arr[X], arr[Y]);
        }
        else {
            Min = 987654321;
            Max = 0;
            getTree(1, 1, N, X, Y);
 
            if (Y - X == Max - Min) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 12919번 - A와 B 2 (C++)  (0) 2023.06.12
[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
반응형

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

 

14449번: Balanced Photo

The first line of input contains N. The next N lines contain h1…hN, each a nonnegative integer at most 1,000,000,000.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr 배열에 키를 저장하고, vector<int> h에 입력으로 주어진 모든 키를 push 합니다.

 

2. h를 오름차순으로 정렬합니다.

 

3. 0부터 N - 1까지 arr 배열을 돌면서 해당 값의 idx를 lower_bound를 통해 구합니다.

 

4. idx + 1 ~ e * N - 1의 구간합을 통해 왼쪽에 있는 값들 중 큰 값을 구하고, cntL에 저장합니다.

 

5. N - 1부터 0까지 위의 3, 4와 같은 방식으로 구하고 cntR에 구간합을 저장합니다.

 

6. cntL[ i ] * 2 < cntR[ i ] 이거나 cntL[ i ] > cntR[ i ] * 2이면 ans++를 해줍니다.

 

7. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[100000];
int cntL[100000];
int cntR[100000];
int segTree[200000];
vector<int> h;
int ret;
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
        
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        h.push_back(arr[i]);
    }
 
    sort(h.begin(), h.end());
 
    for (int i = 0; i < N; i++) {
        auto idx = lower_bound(h.begin(), h.end(), arr[i]) - h.begin();
        updateTree(idx + N);
 
        cntL[i] = getTree(N + idx + 1, 2 * N - 1);
    }
 
    fill(segTree, segTree + 2 * N, 0);
 
    for (int i = N - 1; i >= 0; i--) {
        auto idx = lower_bound(h.begin(), h.end(), arr[i]) - h.begin();
        updateTree(idx + N);
 
        cntR[i] = getTree(N + idx + 1, 2 * N - 1);
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        int L = cntL[i];
        int R = cntR[i];
 
        if (L > R) {
            swap(L, R);
        }
 
        if (2 * L < R) ans++;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
반응형

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

 

11962번: Counting Haybales

Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 세그먼트 트리를 업데이트 해줍니다.

 

2. 구간 합과 구간 최솟값을 각각 저장해 쿼리에 맞게 출력해줍니다.

 

[ 소스코드 ]

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#define ll long long
 
using namespace std;
 
struct node {
    ll sum;
    ll min;
};
 
int N, Q;
int arr[200001];
node segTree[524300];
ll lazy[524300];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node]) {
        segTree[node].sum += lazy[node] * (1LL * e - s + 1);
        segTree[node].min += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
 
    return;
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node].sum = 1LL * arr[s];
        segTree[node].min = 1LL * arr[s];
 
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int C)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node].sum += (1LL * e - s + 1) * (1LL * C);
        segTree[node].min += C;
 
        if (s != e) {
            lazy[node * 2] += C;
            lazy[node * 2 + 1] += C;
        }
 
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, C);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, C);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
ll getSum(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node].sum;
 
    int m = (s + e) / 2;
    
    return getSum(node * 2, s, m, sidx, eidx) + getSum(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
ll getMin(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 11111111111;
    if (sidx <= s && e <= eidx) return segTree[node].min;
 
    int m = (s + e) / 2;
 
    return min(getMin(node * 2, s, m, sidx, eidx), getMin(node * 2 + 1, m + 1, e, sidx, eidx));
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q; i++) {
        char cmd;
        int A, B;
        cin >> cmd >> A >> B;
 
        if (cmd == 'M') {
            cout << getMin(1, 1, N, A, B) << '\n';
        }
        else if (cmd == 'P') {
            int C;
            cin >> C;
 
 
            updateTree(1, 1, N, A, B, C);
        }
        else {
            cout << getSum(1, 1, N, A, B) << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
반응형

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

 

15816번: 퀘스트 중인 모험가

첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q1 ... QN 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. list 배열에 완료한 퀘스트를 저장하고, vector<int> quest에 입력으로 주어진 모든 퀘스트 항목들을 push 하고 중복을 제거합니다.

 

2. for문으로 arr배열을 돌면서 lower_bound를 활용하여 해당 퀘스트가 몇번 째 순서인지 확인하고, segmentTree를 업데이트해줍니다.

 

3. query를 이용하여 R - L + 1 - (L ~ R 구간합)을 통해 답을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct query {
    int cmd;
    int L, R;
};
 
int N, M;
vector<int> quest;
query arr[1000000];
int segTree[6000000];
int list[1000000];
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
 
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int Q;
        scanf("%d", &Q);
 
        list[i] = Q;
        quest.push_back(Q);
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int X;
            scanf("%d", &X);
 
            quest.push_back(X);
            arr[i] = { cmd,X,0 };
        }
        else {
            int L, R;
            scanf("%d %d", &L, &R);
 
            quest.push_back(L);
            quest.push_back(R);
            arr[i] = { cmd,L,R };
        }
    }
 
    sort(quest.begin(), quest.end());
    quest.erase(unique(quest.begin(), quest.end()), quest.end());
    int n = quest.size();
 
    for (int i = 0; i < N; i++) {
        auto idx = lower_bound(quest.begin(), quest.end(), list[i]) - quest.begin();
        updateTree(n + idx);
    }
 
    for (int i = 0; i < M; i++) {
        int cmd = arr[i].cmd;
        int L = arr[i].L;
        int R = arr[i].R;
 
        if (cmd == 1) {
            auto idx = lower_bound(quest.begin(), quest.end(), L) - quest.begin();
            updateTree(n + idx);
        }
        else {
            auto Lidx = lower_bound(quest.begin(), quest.end(), L) - quest.begin();
            auto Ridx = lower_bound(quest.begin(), quest.end(), R) - quest.begin();
 
            printf("%d\n", R - L + 1 - getTree(n + Lidx, n + Ridx));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
반응형

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

 

3006번: 터보소트

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. segmentTree의 리프노드를 모두 1로 채우고 나머지 노드들을 구간합으로 채워줍니다.

 

2. 배열을 입력 받고, 각 수의 위치를 arr 배열에 저장합니다.

 

3. 1부터 N까지 번갈아가며 홀수번째 단계에서는 0 ~ arr[ i ] - 1까지의 구간합을 출력하고, 짝수번째 단계에서는 arr[ i ] + 1 ~ 2N - 1까지의 구간합을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[100001];
int segTree[200000];
 
void updateTree(int idx, int k)
{
    while (idx != 0) {
        segTree[idx] += k;
        idx >>= 1;
    }
}
 
int getTree(int l, int r)
{
    int ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
 
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
        updateTree(N + i, 1);
 
        arr[n] = i;
    }
 
    int L = 1;
    int R = N;
    int cnt = 1;
 
    while (L <= R) {
        if (cnt & 1) {
            printf("%d\n", getTree(N, N + arr[L]) - 1);
            updateTree(N + arr[L], -1);
            L++;
        }
        else {
            printf("%d\n", getTree(N + arr[R], 2 * N - 1) - 1);
            updateTree(N + arr[R], -1);
            R--;
        }
        cnt++;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
반응형

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

 

1280번: 나무 심기

첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. segmentTree를 두개 만들어서 하나에는 모든 좌표의 합을 저장하고, 나머지 하나에는 나무의 개수를 저장합니다.

 

2. idx를 입력 받으면 두 segmentTree를 업데이트 해주고, 0 ~ idx - 1과 idx + 1 ~ 200000까지의 좌표의 합과 나무 개수를 이용하여 모든 나무까지의 거리를 구합니다.

 

3. 현재 좌표의 왼쪽 나무들까지의 합을 구할 때는 현재 좌표 * 나무 개수 - 왼쪽 나무의 좌표들의 합으로 구하고, 오른쪽 나무들까지의 합을 구할 때는 오른쪽 나무의 좌표들의 합 - 현재 좌표 * 나무의 개수를 더해 구합니다.

 

4. ans에 3에서 구한 값을 곱해주고 1,000,000,007로 모듈러 연산을 한 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
#define M 1000000007
 
using namespace std;
 
int N;
ll segTree[400002];
ll segTree2[400002];
ll ans = 1;
 
void updateTree(ll idx)
{
    ll temp = idx - 200001;
 
    while (idx != 0) {
        segTree[idx] += temp;
        segTree2[idx]++;
        idx >>= 1;
    }
}
 
pair<ll,ll> getTree(int l, int r)
{
    ll ret = 0;
    ll ret2 = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            ret2 += segTree2[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            ret2 += segTree2[r];
            r--;
        }
 
        l >>= 1;
        r >>= 1;
    }
 
    return { ret, ret2 };
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        ll idx;
        scanf("%lld", &idx);
        pair<ll, ll> temp;
        pair<ll, ll> temp2;
 
        updateTree(idx + 200001);
 
        if (i != 0) {
            if (idx == 0) {
                temp = getTree(200001 + idx + 1, 400001);
                ans = ((ans % M) * ((temp.first - idx * temp.second) % M)) % M;
            }
            else if (idx == 200000) {
                temp = getTree(200001, 200001 + idx - 1);
                ans = ((ans % M) * ((idx * temp.second - temp.first) % M)) % M;
            }
            else {
                temp = getTree(200001, 200001 + idx - 1);
                temp2 = getTree(200001 + idx + 1, 400001);
                ans = ((ans % M) * ((temp2.first - idx * temp2.second + idx * temp.second - temp.first) % M)) % M;
            }
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
반응형

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

 

14287번: 회사 문화 3

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. dfs를 통해 각 노드가 몇 번에서 시작해서 몇 번에서 끝나는지 오일러 경로 테크닉을 이용하여 s[ n ], e[ n ]에 저장합니다.

 

2. 세그먼트 트리를 이용하여 각 노드의 값을 업데이트 해주고, 구간합을 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int n, m;
int segTree[200000];
int s[100001];
int e[100001];
int cnt = -1;
vector<int> list[100001];
 
void dfs(int num)
{
    s[num] = ++cnt;
 
    for (int& next : list[num]) {
        dfs(next);
    }
 
    e[num] = cnt;
}
 
void updateTree(int node, int w)
{
    while (node != 0) {
        segTree[node] += w;
        node >>= 1;
    }
}
 
int getTree(int left, int right)
{
    int ret = 0;
 
    while (left <= right) {
        if (left % 2 == 1) {
            ret += segTree[left];
            left += 1;
        }
        if (right % 2 == 0) {
            ret += segTree[right];
            right -= 1;
        }
 
        left >>= 1;
        right >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        int parent;
        scanf("%d", &parent);
 
        if (parent != -1) {
            list[parent].push_back(i);
        }
    }
 
    dfs(1);
 
    for (int j = 0; j < m; j++) {
        int com, i;
        scanf("%d %d", &com, &i);
 
        if (com == 1) {
            int w;
            scanf("%d", &w);
            updateTree(s[i] + n, w);
        }
        else {
            printf("%d\n", getTree(n + s[i], n + e[i]));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
반응형

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

 

14419번: Foehn Phenomena

Initially, the altitudes of the Spot 0, 1, 2, 3 are 0, 4, 1, 8, respectively. After the tectonic movement on the first day, the altitudes become 0, 6, 3, 8, respectively. At that moment, the temperatures of the wind are 0, -6, 0, -5, respectively.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr 배열에 각 언덕의 높이를 저장하고, diff 배열에 arr[ i ] - arr[ i + 1 ]의 값을 저장합니다.

 

2. L, R, X가 입력되면 diff[ L - 1 ]의 값에 X를 빼주고, R != N일 때 diff[ R ]의 값에 X를 더해줍니다.

 

3. 해당 값을 기준으로 segmentTree를 업데이트해주고, segTree[ 1 ]의 값을 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, Q, S, T;
ll arr[200001];
ll diff[200000];
ll segTree[400000];
 
void updateTree(int i)
{
    if (diff[i] < 0) {
        segTree[i + N] = diff[i] * S;
    }
    else {
        segTree[i + N] = diff[i] * T;
    }
 
    int temp = i + N;
    temp >>= 1;
    while (temp != 0) {
        segTree[temp] = segTree[temp << 1] + segTree[temp << 1 | 1];
        temp >>= 1;
    }
}
 
int main()
{
    scanf("%d %d %d %d", &N, &Q, &S, &T);
 
    for (int i = 0; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        diff[i] = arr[i] - arr[i + 1];
    }
 
    for (int i = 0; i < N; i++) {
        if (arr[i] < arr[i + 1]) {
            segTree[i + N] = (arr[i] - arr[i + 1]) * S;
        }
        else {
            segTree[i + N] = (arr[i] - arr[i + 1]) * T;
        }
    }
 
    for (int i = N - 1; i >= 1; i--) {
        segTree[i] = segTree[i << 1] + segTree[i << 1 | 1];
    }
 
    for (int i = 0; i < Q; i++) {
        int L, R;
        ll X;
        scanf("%d %d %lld", &L, &R, &X);
 
        diff[L - 1] -= X;
        if(R != N) diff[R] += X;
 
        updateTree(L - 1);
        if (R != N) updateTree(R);
        printf("%lld\n", segTree[1]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03

+ Recent posts

티스토리툴바