반응형

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

 

12844번: XOR

크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

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

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

rudalsd.tistory.com

 

1. 세그먼트 트리와 lazy값을 저장할 배열을 만듭니다.

 

2. 현재 쿼리의 노드 개수가 홀수일 때만 XOR을 해주고, 짝수라면 lazy 값만 넘겨줍니다.

 

3. 느리게 갱신되는 세그먼트 트리를 활용하여 Update를 하고 XOR 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[500001];
int segTree[1050000];
int lazy[1050000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = segTree[node * 2] ^ segTree[node * 2 + 1];
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        if ((e - s + 1) % 2 == 1) {
            segTree[node] ^= lazy[node];
        }
 
        if (s != e) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int k)
{
    updateLazy(node, s, e);
 
    if (e < sidx || s > eidx) return;
    if (sidx <= s && e <= eidx) {
        lazy[node] ^= k;
        updateLazy(node, s, e);
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, k);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, k);
 
    segTree[node] = segTree[node * 2] ^ segTree[node * 2 + 1];
}
 
int getTree(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (e < sidx || s > eidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    return getTree(node * 2, s, m, sidx, eidx) ^ getTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 0, N - 1);
 
    scanf("%d", &M);
 
    for (int q = 0; q < M; q++) {
        int n, i, j, k;
        scanf("%d %d %d", &n, &i, &j);
 
        if (n == 1) {
            scanf("%d", &k);
            updateTree(1, 0, N - 1, i, j, k);
        }
        else {
            printf("%d\n", getTree(1, 0, N - 1, i, j));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
반응형

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

 

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

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
#include<iostream>
 
using namespace std;
 
int arr[10000001];
int N, L;
 
int getTree(int left, int right)
{
    left += N;
    right += N;
    int ret = 1000000000;
 
    while (left <= right) {
        if (left & 1) {
            ret = min(arr[left], ret);
            left += 1;
        }
        if (~right & 1) {
            ret = min(arr[right], ret);
            right -= 1;
        }
        left >>= 1;
        right >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> L;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[N + i];
    }
 
    for (int i = N - 1; i >= 1; i--) {
        arr[i] = min(arr[i << 1], arr[i << 1 | 1]);
    }
 
    for (int i = 0; i < N; i++) {
        cout << getTree(max(0, i - L + 1), i) << ' ';
    }
}
cs

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
반응형

1. 비재귀 세그먼트 트리 (Segment Tree)

 

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

 

2. 비재귀 세그먼트 트리 구현

 

항의 개수가 N개라면 리프노드는 N번 노드부터 2N - 1번 노드까지 입니다. 이후 N번 노드부터 1번 노드까지 for문을 통해 돌면서 해당 노드의 왼쪽 노드는 i << 1, 오른쪽 노드는 i << 1 | 1로 표현됩니다.

 

따라서, 합을 구하려면 segTree[node] = segTree[ node << 1 ] + segTree[ node << 1 | 1 ] 로 표현해줍니다.

 

3. 비재귀 세그먼트 트리 구간합 구하기

구간에서 왼쪽 경계의 노드 번호가 짝수라면 부모 노드가 반드시 구간에 포함되고, 홀수라면 부모 노드가 구간에 절대 포함되지 않습니다. 부모 노드가 구간에 절대 포함되지 않을 때 왼쪽 경계의 값에 1을 더해줍니다.

 

구간에서 오른쪽 경계의 노드 번호가 짝수라면 부모 노드가 구간에 절대 포함되지 않고, 홀수라면 부모 노드가 반드시 구간에 포함됩니다. 부모 노드가 구간에 절대 포함되지 않을 때 오른쪽 경계의 값에 1을 빼줍니다.

 

이를 왼쪽 경계의 값과 오른쪽 경계의 값이 교차될 때까지 수행하고, 교차된다면 반복문을 탈출해줍니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)  (0) 2023.08.07
[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07
[ 자료구조 ] 세그먼트 트리 (Segment Tree)  (0) 2022.07.02
반응형

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

 

17400번: 깃발춤

첫 번째 줄에는 깃발춤을 진행하는 공연자의 명수인 자연수 N과 상황 변화의 개수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ Q ≤ 300,000) 두 번째 줄에는 정수 c1, c2, ..., cN

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 번갈아가면서 춤을 추므로 segmentTree[ node ].first에는 idx % 2 == 0인 값을 second에는 idx % 2 == 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
 
int N, Q;
int arr[300001];
pair<ll, ll> segTree[1050000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        if (s % 2 == 0) {
            segTree[node].first = arr[s];
        }
        else {
            segTree[node].second = arr[s];
        }
        return;
    }
 
    int m = (s + e) / 2;
 
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node].first = segTree[node * 2].first + segTree[node * 2 + 1].first;
    segTree[node].second = segTree[node * 2].second + segTree[node * 2 + 1].second;
}
 
pair<ll,ll> getTree(int node, int s, int e, int sidx, int eidx)
{
    if (eidx < s || e < sidx) return { 0,0 };
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
 
    pair<ll, ll> left = getTree(node * 2, s, m, sidx, eidx);
    pair<ll, ll> right = getTree(node * 2 + 1, m+1, e, sidx, eidx);
    
    return { left.first + right.first, left.second + right.second };
}
 
void updateTree(int node, int s, int e, int idx, int x)
{
    if (s > idx || e < idx) return;
    if (idx % 2 == 0) {
        segTree[node].first += x;
    }
    else {
        segTree[node].second += x;
    }
 
    if (s != e) {
        int m = (s + e) / 2;
 
        updateTree(node * 2, s, m, idx, x);
        updateTree(node * 2 + 1, m + 1, e, idx, x);
    }
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q; i++) {
        int com, L, R;
        scanf("%d %d %d", &com, &L, &R);
 
        if (com == 1) {
            pair<ll, ll> temp = getTree(1, 1, N, L, R);
            printf("%lld\n", abs(temp.first - temp.second));
        }
        else {
            updateTree(1, 1, N, L, R);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 22862번 - 가장 긴 짝수 연속한 부분 수열 (large) (C++)  (0) 2023.04.09
[ 백준 ] 2230번 - 수 고르기 (C++)  (0) 2023.04.08
[ 백준 ] 1306번 - 달려라 홍준 (C++)  (0) 2023.04.06
[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
반응형

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

 

1306번: 달려라 홍준

첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 각각의 노드에 해당 범위의 최댓값을 저장하고, for문을 통해 인덱스를 슬라이싱 하면서 원하는 범위에서의 최댓값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<cmath>
 
using namespace std;
 
int N, M;
int segTree[2111111];
int arr[1000001];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = max(segTree[node * 2], segTree[node * 2 + 1]);
}
 
int getTree(int node, int s, int e, int sidx, int eidx)
{
    if (eidx < s || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    int left = getTree(node * 2, s, m, sidx, eidx);
    int right = getTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return max(left, right);
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = M; i <= N - M + 1; i++) {
        printf("%d\n", getTree(1, 1, N, i - (M - 1), i + M - 1));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2230번 - 수 고르기 (C++)  (0) 2023.04.08
[ 백준 ] 17400번 - 깃발춤 (C++)  (0) 2023.04.07
[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
반응형

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

 

11658번: 구간 합 구하기 3

첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 이 문제를 풀기 위해서 2차원 세그먼트 트리를 만듭니다. (segTree [ x ][ y ])

 

2. segTree[ x ]의 리프노드에 x행의 값들을 다시 세그먼트 트리의 형식으로 저장합니다.

 

[출처] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jh20s&logNo=221351546136

 

3. 특정 좌표의 값을 업데이트할 때 x행의 세그먼트 트리 노드를 찾은 후 y열의 세그먼트 트리 노드 값을 바꿔줍니다.

 

4. 구간 합을 구할 때도 3과 마찬가지로 x행의 세그먼트 트리 노드를 찾은 후 y열의 세그먼트 트리 노드의 구간합을 구해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int segTree[2050][2050];
int arr[1025][1025];
 
void updateTreeY(int node, int s, int e, int x, int y, int diff)
{
    if (y < s || e < y) return;
    segTree[x][node] += diff;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTreeY(node * 2, s, m, x, y, diff);
        updateTreeY(node * 2+1, m+1, e, x, y, diff);
    }
}
 
void updateTreeX(int node, int s, int e, int x, int y, int diff)
{
    if (x < s || e < x) return;
    updateTreeY(1, 1, N, node, y, diff);
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTreeX(node * 2, s, m, x, y, diff);
        updateTreeX(node * 2 + 1, m + 1, e, x, y, diff);
    }
}
 
int sumTreeY(int node, int s, int e, int x, int y1, int y2)
{
    if (y2 < s || e < y1) return 0;
    if (y1 <= s && e <= y2) return segTree[x][node];
 
    int m = (s + e) / 2;
    int left = sumTreeY(node * 2, s, m, x, y1, y2);
    int right = sumTreeY(node * 2 + 1, m + 1, e, x, y1, y2);
 
    return left + right;
}
 
int sumTreeX(int node, int s, int e, int x1, int y1, int x2, int y2)
{
    if (x2 < s || e < x1) return 0;
    if (x1 <= s && e <= x2) return sumTreeY(1, 1, N, node, y1, y2);
 
    int m = (s + e) / 2;
    int left = sumTreeX(node * 2, s, m, x1, y1, x2, y2);
    int right = sumTreeX(node * 2 + 1, m + 1, e, x1, y1, x2, y2);
 
    return left + right;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
            updateTreeX(1, 1, N, i, j, arr[i][j]);
        }
    }
 
    for (int i = 0; i < M; i++) {
        int w;
        scanf("%d", &w);
 
        if (w == 0) {
            int x, y, c;
            scanf("%d %d %d", &x, &y, &c);
            int diff = c - arr[x][y];
            arr[x][y] = c;
            updateTreeX(1, 1, N, x, y, diff);
        }
        else {
            int ans = 0;
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            printf("%d\n", sumTreeX(1, 1, N, x1, y1, x2, y2));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15971번 - 두 로봇 (C++)  (0) 2023.02.10
[ 백준 ] 2637번 - 장난감 조립 (C++)  (0) 2023.02.09
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
[ 백준 ] 2211번 - 네트워크 복구 (C++)  (0) 2023.02.06
[ 백준 ] 17835번 - 면접보는 승범이네 (C++)  (0) 2023.02.05
반응형

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

 

3770번: 대한민국

입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. pair < int, int > arr [ 400001 ]를 만들어 수를 입력받고, arr배열을 오름차순으로 정렬합니다.

 

2. for문을 통해 반복하면서 arr[ i ].second를 idx로 세그먼트 트리를 갱신하고, arr [ i ].second + 1부터 M까지의 구간 합을 구해 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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int T;
pair<int, int> arr[400001];
 
void updateTree(int node, int s, int e, int idx, ll* segTree)
{
    if (idx < s || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx, segTree);
        updateTree(node * 2 + 1, m + 1, e, idx, segTree);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx, ll* segTree)
{
    if (sidx > e || eidx < s) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx, segTree);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx, segTree);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++) {
        int N, M, K;
        ll segTree[2050] = { 0 };
        scanf("%d %d %d", &N, &M, &K);
 
        for (int i = 0; i < K; i++) {
            scanf("%d %d", &arr[i].first, &arr[i].second);
        }
 
        sort(arr, arr + K);
 
        ll ans = 0;
 
        for (int i = 0; i < K; i++) {
            updateTree(1, 1, M, arr[i].second, segTree);
            ans += sumTree(1, 1, M, arr[i].second + 1, M, segTree);
        }
 
        printf("Test case %d: %lld\n", t, ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
반응형

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

 

9463번: 순열 그래프

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. 둘째 줄과 셋째 줄에는 두 순열이 주어진다. 순열은 {1, 2, ..., n}으로 이루어져 있고, 공백으로 구분

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 첫 줄의 num을 입력받고, arr [ num ] = i로 저장합니다.

 

2. 두 번째 줄의 num을 입력받고, arr [ num ]을 idx로 세그먼트 트리를 갱신합니다.

 

3. arr [ num ] + 1부터 n까지 구간 합을 ans에 더해줍니다.

 

4. 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
#include<iostream>
#define ll long long
 
using namespace std;
 
int T;
ll segTree[263000];
int arr[100001];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int n;
        scanf("%d", &n);
        fill_n(segTree, 263000, 0);
        
        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            arr[num] = i;
        }
 
        ll ans = 0;
 
        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            updateTree(1, 1, n, arr[num]);
            ans += sumTree(1, 1, n, arr[num] + 1, n);
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
반응형

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

 

10090번: Counting Inversions

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 입력받은 수를 인덱스로 segment tree를 업데이트합니다.

 

2. 입력받은 수 + 1부터 N까지 구간 합을 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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll segTree[2100000];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    ll ans = 0;
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
 
        updateTree(1, 1, N, n);
        ans += sumTree(1, 1, N, n + 1, N);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
반응형

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

 

1615번: 교차개수세기

첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 입력받은 수를 첫번 째 수를 기준으로 오름차순으로 정렬합니다.

 

2. for문을 통해 반복하면서 두번 째 수를 인덱스로 segment tree를 업데이트 합니다.

 

3. 이후 두번 째 수부터 N까지 구간 합을 ans에 더해줍니다.

 

4. 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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int N, M;
pair<int, int> arr[2000000];
ll segTree[5000];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node] += 1;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    sort(arr, arr + M);
 
    ll ans = 0;
 
    for (int i = 0; i < M; i++) {
        int cur = arr[i].second;
        
        updateTree(1, 1, N, cur);
        ans += sumTree(1, 1, N, cur + 1, N);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18

+ Recent posts

티스토리툴바