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

 

처음 주어지는 배열과 다르게 배치된 쌍의 갯수를 구하는 문제로 inversion counting 방식으로 접근할 수 있습니다.

inversion counting이란 순서가 바뀐 순서쌍을 구하는데 사용되는 기법입니다.

즉 자신보다 작지만 뒤에 몇 명이 서있는지 구한다거나 그런 문제들을 이 방식을 사용할 수 있습니다.

 

우선 입력이 문자열로 되어있으니 map을 활용하여 첫 번째 배열을 입력받는 순서대로 정수 인덱스로 변경해줍니다.

그 다음 두 번째 배열은 첫 번째 배열에서 구한 인덱스 번호로 변경합니다.

두 번째 입력에서 구한 정수 배열로 트리를 만들도록 합니다.

이 때 트리에 수를 넣어주면서 자신보다 크지만 먼저 들어온 수들의 갯수를 세어주면 됩니다.

배열이 2 3 1 순서대로 저장한다고 가정하면 1을 트리에 넣을때 이미 들어와있던 2, 3을 카운팅 해주는 것입니다.

 

일반적인 map을 사용한 코드의 채점현황입니다.

unordered_map으로 변경한 코드의 채점현황입니다.

이 문제처럼 순서가 중요하지 않고 조회가 많이 발생하는 경우 unordered_map을 사용하는게 더 효율적이라는 것을 알 수 있었습니다.

 

 

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
#include <iostream>
#include <unordered_map>
#include <string>
#include <cstring>
#define MAX 100001
using namespace std;
typedef long long ll;
 
unordered_map<stringint> m;
int idxList[MAX];
ll tree[MAX << 2];
int N;
 
void init() {
    m.clear();
    memset(tree, 0sizeof(tree));
}
 
ll update(int node, int l, int r, int idx, int diff) {
    if (idx < l || r < idx) return tree[node];
    if (l == r) return ++tree[node];
 
    int m = (l + r) >> 1;
    return tree[node] = update(node << 1, l, m, idx, diff) + update((node << 1+ 1, m + 1, r, idx, diff);
}
 
ll query(int node, int l, int r, int s, int e) {
    if (l > e || r < s) return 0LL;
    if (s <= l && r <= e) return tree[node];
 
    int m = (l + r) >> 1;
    return query(node << 1, l, m, s, e) + query((node << 1+ 1, m + 1, r, s, e);
}
 
void func() {
    ll ret = 0LL;
    for (int i = 0; i < N; i++) {
        ret += query(11, N, idxList[i] + 1, N);
        update(11, N, idxList[i], 1);
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    if (!N) exit(0);
    
    string str;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        cin >> str;
        m[str] = ++cnt;
    }
 
    for (int i = 0; i < N; i++) {
        cin >> str;
        idxList[i] = m[str];
    }
}
 
int main() {
    cin.tie(nullptr); cout.tie(nullptr);
    ios::sync_with_stdio(false);
 
    while (1) {
        input();
        func();
        init();
    }
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 8330 순열  (0) 2024.07.21
boj 1517 버블 소트  (0) 2024.06.16
boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02

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

 

수열이 a1, a2, ..., an 으로 주어졌을때 1 ~ ai 범위의 숫자를 적절하게 골라서 1 ~ N의 수가 하나씩 등장하도록 만들어야 합니다.

 

5
3 4 3 2 5

즉 이런 수열이 주어졌을 때

a1은 1 ~ 3 중에서 2

a2는 1 ~ 4 중에서 4

a3은 1 ~ 3 중에서 3

a4는 1 ~ 2 중에서 1

a5는 1 ~ 5 중에서 5

이렇게 골라서 1 ~ N까지 하나씩 등장하도록 순열을 만들 수 있습니다.

그리고 수열을 M번 수정하여 각각 수정된 수열에서도 위처럼 1 ~ N을 만들 수 있는지 구하는 문제입니다.

 

이 문제에서 저는 Segment Tree Lazy를 사용했고, 트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.

1 ~ 5가 있다면

1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있습니다.

5 5 5 5 5가 입력된다면 5에서 수를 5번 고른다는 뜻입니다.

만약 4 4 4 4 4가 입력된다면 5개의 4에서 1 ~ 5를 하나씩 만들 수가 없게 되는거죠.

그렇게 i ~ N을 +1씩 업데이트를 해주고, 각각 노드에서의 최솟값으로 갱신하도록 합니다.

 

그 다음에는 최초로 주어진 수열에서 1 ~ N을 만들 수 있는지 먼저 확인합니다.

list[i]를 사용한게 되기 때문에 list[i] ~ N의 범위에 -1로 업데이트를 시켜줍니다.

트리를 최솟값으로 저장한 이유는 이 연산 과정에서 해당 값의 카운트가 음수인 경우를 빠르게 캐치하기 위해서입니다.

수열의 모든 수를 대상으로 업데이트가 끝난다면 query 함수를 이용하여 트리의 최솟값을 가져옵니다.

최솟값이 0 이상이면 순열을 만들 수 있고, 음수면 만들 수 없습니다.

 

다음 할 작업은 idx번째 수를 x로 변경하는 것입니다.

처음에는 위에서 -1로 업데이트를 한걸 되돌려야 하는지 고민했었는데 결과적으로 시간초과가 뜨더라고요!

N은 20만, M은 50만이기 때문에 시간초과가 당연한거였습니다.

20만개의 수를 50만번 업데이트 해야되니까요.. ㅎ

 

좀더 고민했을때는 트리에는 수열에 대한 카운팅이 각각 진행된 상태였고,

어차피 업데이트되는 idx번째 수에 대해서만 카운팅을 바꿔주면 된다는 결론이 나왔습니다.

그래서 수를 업데이트 하기 전에 기존 list[idx]의 범위에 대한 업데이트를 +1로 진행해주고,

새로운 값인 x의 범위에 대한 업데이트를 -1으로 진행해주면 새로운 수열에서의 카운팅 작업이 완료되는 것입니다.

마지막에는 업데이트된 트리의 최솟값을 가져와서 0 이상이면 `TAK`을, 음수면 `NIE`를 출력해주시면 되겠습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;
 
int list[MAX];
int tree[MAX << 2];
int lazy[MAX << 2];
int N, M;
 
void lazyUpdate(int node, int l, int r) {
    if (!lazy[node]) return;
    tree[node] += lazy[node];
    if (l != r) {
        lazy[node << 1+= lazy[node];
        lazy[(node << 1+ 1+= lazy[node];
    }
    lazy[node] = 0;
}
 
int update(int node, int l, int r, int s, int e, int diff) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return tree[node];
    if (s <= l && r <= e) {
        lazy[node] += diff;
        lazyUpdate(node, l, r);
        return tree[node];
    }
 
    int m = (l + r) >> 1;
    return tree[node] = min(update(node << 1, l, m, s, e, diff), update((node << 1+ 1, m + 1, r, s, e, diff));
}
 
int query(int node, int l, int r, int s, int e) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return 0;
    if (s <= l && r <= e) return tree[node];
 
    int m = (l + r) >> 1;
    return min(query(node << 1, l, m, s, e), query((node << 1+ 1, m + 1, r, s, e));
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        update(11, N, i, N, 1);
    }
 
    for (int i = 0; i < N; i++) {
        update(11, N, list[i], N, -1);
    }
}
 
void print() {
    if (query(11, N, 1, N) >= 0cout << "TAK\n";
    else cout << "NIE\n";
}
 
void func() {
    init();
    print();
 
    int idx, x;
    while (M--) {
        cin >> idx >> x;
        update(11, N, list[idx - 1], N, 1);
        update(11, N, x, N, -1);
        list[idx - 1= x;
        print();
    }
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    cin >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 4442 빌보의 생일  (0) 2024.08.01
boj 1517 버블 소트  (0) 2024.06.16
boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02

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

 

예전에 재채점되어 틀린 문제를 다시 풀게 되었습니다.

 

덕분에 이 글은 내리게되었네요 ㅠ

이전에는 merge sort로 풀었던 문제라 그건 수정해서 AC를 받았고, 이번에는 다른 방법으로 접근했습니다.

 

이 문제처럼 버블 소트의 특징을 이해하고 있다면 해결할 수 있습니다.

버블소트는 앞뒤의 수를 비교하여 앞의 숫자가 크면 두 수의 위치를 swap 하게 됩니다.

이 문제는 그 swap의 횟수를 구하는 문제로 본인보다 앞에 있지만 더 큰수의 갯수를 세어주면 된다는 결론이 나옵니다.

 

그러면 입력으로 주어지는 정수들로 세그먼트 트리를 이용할 수 있습니다.

본인보다 먼저 트리에 들어간 수 중에 본인보다 큰 수의 갯수를 카운팅하도록 합니다.

하지만 입력의 범위는 절댓값이 10억이라서 배열로 표현하기는 어려울 수 있습니다.

그렇다면 N이 50만이라는 것을 이용하여 좌표압축 기법을 생각할 수 있습니다.

 

https://whyeskang.com/362

 

좌표 압축 (Coordinate Compression)

3년전에 대학 과제로 좌표 압축 기법을 활용하는 문제가 나왔었지만 이해를 못해서 풀지 못했습니다. 지금와서 보니 생각보다 간단했고, 정리하면서 포스팅합니다. 우선 좌표압축이란, 수의 범

whyeskang.com

위 게시글을 참고하시면 문제없이 좌표압축 기법을 사용하실 수 있을 것입니다.

 

좌표압축이 끝났다면 1 ~ N의 범위 내에서 본인보다 큰 수의 갯수를 세그먼트 트리를 활용하여 구할 수 있습니다.

입력이 들어온 순서대로 query 함수를 이용하여 갯수를 구하고, update를 시켜주면 차례대로 구할 수 있습니다.

 

 

[C++]

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
#include <iostream>
#include <algorithm>
#define MAX 500001
using namespace std;
typedef long long ll;
typedef pair<intint> pii;
 
pii list[MAX];
ll tree[MAX << 2];
int N;
 
void compress() {
    sort(list, list + N);
    int pre = 1e9 + 1;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (pre != list[i].first) cnt++;
        pre = list[i].first;
        list[i].first = cnt;
    }
    sort(list, list + N, [](pii a, pii b) {
        return a.second < b.second;
    });
}
 
ll update(int node, int l, int r, int x) {
    if (x < l || r < x) return tree[node];
    if (l == r) return ++tree[node];
 
    int m = (l + r) >> 1;
    return tree[node] = update(node << 1, l, m, x) + update((node << 1+ 1, m + 1, r, x);
}
 
ll query(int node, int l, int r, int s, int e) {
    if (s <= l && r <= e) return tree[node];
    if (l > e || s > r) return 0;
 
    int m = (l + r) >> 1;
    return query(node << 1, l, m, s, e) + query((node << 1+ 1, m + 1, r, s, e);
}
 
void func() {
    compress();
 
    ll ret = 0;
    for (int i = 0; i < N; i++) {
        ret += query(11, N, list[i].first + 1, N);
        update(11, N, list[i].first);
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first;
        list[i].second = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

 

Java로 문제를 풀다가 의문이 든게 있는데

 

Arrays.sort(array, from, to, comparator) 메소드와

Arrays.sort(array, comparator) 메소드의 성능 차이에 대해 궁금해졌습니다.

AC를 받은 코드는 Arrays.sort(array, from, to, comparator) 메소드를 사용한 코드고,

TLE를 받은 코드는 Arrays.sort(array, comparator) 메소드를 사용한 코드입니다.

그거 말고는 차이가 없는데 결과가 다르게 나오는 상황이라.. 당황했던 기억이 있습니다.

이걸 시스템상의 문제로 짚고 넘어가도 될만한 것인지는 잘 모르겠네요. 그냥 억까라고 해야하나 이걸

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    private static int list[][];
    private static long tree[];
    private static int N;
 
    private static void compress() {
        Arrays.sort(list, 0, N, (o1, o2) -> {
            if (o1[0== o2[0]) return o1[1- o2[1];
            return o1[0- o2[0];
        });
        int pre = Integer.MAX_VALUE;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (pre != list[i][0]) cnt++;
            pre = list[i][0];
            list[i][0= cnt;
        }
        Arrays.sort(list, 0, N, Comparator.comparingInt(o -> o[1]));
    }
 
    private static long update(int node, int l, int r, int x) {
        if (x < l || r < x) return tree[node];
        if (l == r) return ++tree[node];
 
        int m = (l + r) >> 1;
        return tree[node] = update(node << 1, l, m, x) + update((node << 1+ 1, m + 1, r, x);
    }
 
    private static long query(int node, int l, int r, int s, int e) {
        if (s <= l && r <= e) return tree[node];
        if (l > e || s > r) return 0L;
 
        int m = (l + r) >> 1;
        return query(node << 1, l, m, s, e) + query((node << 1+ 1, m + 1, r, s, e);
    }
 
    private static void func() {
        compress();
 
        long ret = 0;
        for (int i = 0; i < N; i++) {
            ret += query(11, N, list[i][0+ 1, N);
            update(11, N, list[i][0]);
        }
        System.out.println(ret);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
        tree = new long[(N << 2+ 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i][0= Integer.parseInt(st.nextToken());
            list[i][1= i;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 4442 빌보의 생일  (0) 2024.08.01
boj 8330 순열  (0) 2024.07.21
boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02

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

 

17131번: 여우가 정보섬에 올라온 이유

첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다.

www.acmicpc.net

알고리즘 정말 오랜만이네요.

 

만들어야 하는 별자리는 V 모양이며, V를 회전한 모양은 포함하지 않습니다. (ex. < > ^ ㄱ ㄴ 모양은 X)

여기서 가로를 x, 세로를 y 축이라고 가정했을 때

예시 기준 a, b, c만 별자리로 인정할 수 있습니다.

 

그리고 문제에서도 a.x < b.x < c.x이고 a.y > b.y < c.y 라고 친절히 설명도 해줍니다.

이 조건에서 라인 스위핑 기법을 활용하기 위해 y 값 기준 내림차순 정렬이 필요하다는 것을 알 수 있습니다.

그러면 같은 y값들을 가지고 먼저 놓여진 별들x 값이 작은 별들의 갯수와 x 값이 큰 별들의 갯수를 곱하면 별자리의 갯수를 구할 수 있습니다.

어떤 정해진 범위 내에서 특정 범위의 값을 구한다고 했을때 구간합을 떠올릴 수 있습니다.

구간합을 구하는 알고리즘은 세그먼트 트리가 있습니다.

그러면 이 문제는 세그먼트 트리 + 라인 스위핑을 활용하여 해결할 수 있습니다.

 

로직의 순서는

1. 위에서 설명한것처럼 y 좌표 기준으로 내림차순 정렬합니다.

2. 같은 y값을 가진 별들을 가지고 x 값이 작은/큰 별들의 갯수를 구합니다.

3. 그 다음 같은 y값을 가진 별들을 한꺼번에 트리에 업데이트를 합니다.

 

이게 끝이지만 주의할점은

같은 y값을 가진 모든 별들이 2번 과정이 끝난 후에 3번 과정을 같이 진행해야합니다.

이 풀이의 핵심은 2번 과정에 들어왔을때 트리에 있는 값들은 모두 자신보다 y 값이 큰 별 이라는 것입니다.

그래서 저는 같은 y값을 가진 별들을 벡터에 넣어주고, 3번 과정에서 한꺼번에 업데이트를 했습니다.

 

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 200001
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<intint> pii;
 
ll tree[MAX << 3];
pii list[MAX];
int N;
 
bool cmp(pii a, pii b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
ll update(int node, int l, int r, int idx) {
    if (idx < l || r < idx) return tree[node];
    if (l == r) {
        return tree[node] = tree[node] + 1;
    }
 
    int m = (l + r) >> 1;
    return tree[node] = update(node << 1, l, m, idx) + update((node << 1+ 1, m + 1, r, idx);
}
 
ll query(int node, int l, int r, int s, int e) {
    if (s <= l && r <= e) return tree[node];
    if (e < l || r < s) return 0LL;
 
    int m = (l + r) >> 1;
    return query(node << 1, l, m, s, e) + query((node << 1+ 1, m + 1, r, s, e);
}
 
void func() {
    sort(list + 1, list + 1 + N, cmp);
 
    ll ret = 0;
    int pre = list[1].second;
    vector<int> v;
    for (int i = 1; i <= N; i++) {
        int m = list[i].first;
        if (pre == list[i].second) {
            v.push_back(m);
        }
        else {
            for (auto x : v) {
                update(10, (MAX - 1<< 1, x);
            }
            v.clear();
            pre = list[i].second;
            v.push_back(m);
        }
        ret = (ret + query(10, (MAX - 1<< 10, m - 1* query(10, (MAX - 1<< 1, m + 1, (MAX - 1<< 1)) % MOD;
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i].first >> list[i].second;
        list[i].first += (MAX - 1);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 8330 순열  (0) 2024.07.21
boj 1517 버블 소트  (0) 2024.06.16
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02
boj 16993 연속합과 쿼리  (0) 2022.08.29

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

 

12895번: 화려한 마을

첫 번째 줄에 N, T, Q (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 30, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 개수, 사용할 색의 개수, 작업의 개수를 의미한다. 두 번째 줄부터 작

www.acmicpc.net

출력은 l ~ r 구간에 칠해져 있는 색의 가짓수, 집에 칠할 수 있는 색은 최대 30가지입니다.

업데이트와 쿼리가 섞여 있으므로 오프라인 쿼리 및 mo's 알고리즘은 사용하지 못하고, 세그먼트 트리 lazy를 사용합니다.

트리에는 해당 구간에 칠해져 있는 색의 가짓수를 비트 필드로 저장합니다.

 

우선 모든 집에 1이 칠해져 있는 상태로 시작합니다. init 함수에서 초기화를 진행합니다.

type == C면 l ~ r 구간에 업데이트를 진행합니다.

원래 칠해져 있던 색을 지우고, 새로운 색을 채워야 하므로 tree[node]에 해당 색으로 변경해줍니다.

type == Q면 l ~ r 구간에 칠해져 있는 색의 가짓수를 출력합니다.

트리에는 비트 필드를 저장했으니 시프트연산을 하면서 1의 갯수를 출력합니다.

lazyUpdate는 모든 update, query 시 먼저 진행합니다.

 

이 문제는 l > r인 입력도 주어지니 l < r이 되도록 swap을 해야합니다.

 

 

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
#include <iostream>
#define MAX 100001
using namespace std;
 
int tree[MAX * 4], lazy[MAX * 4];
int N, M, K;
 
void init(int node, int s, int e) {
    if (s == e) {
        tree[node] = 1;
        return;
    }
 
    int m = (s + e) / 2;
    init(node * 2, s, m);
    init(node * 2 + 1, m + 1, e);
    tree[node] = tree[node * 2| tree[node * 2 + 1];
}
 
void lazyUpdate(int node, int s, int e) {
    if (!lazy[node]) return;
 
    tree[node] = lazy[node];
    if (s != e) {
        lazy[node * 2= lazy[node];
        lazy[node * 2 + 1= lazy[node];
    }
    lazy[node] = 0;
}
 
void update(int node, int s, int e, int l, int r, int k) {
    lazyUpdate(node, s, e);
    if (s > r || l > e) return;
    if (l <= s && e <= r) {
        lazy[node] = (1 << k);
        lazyUpdate(node, s, e);
        return;
    }
 
    int m = (s + e) / 2;
    update(node * 2, s, m, l, r, k);
    update(node * 2 + 1, m + 1, e, l, r, k);
    tree[node] = tree[node * 2| tree[node * 2 + 1];
}
 
int query(int node, int s, int e, int l, int r) {
    lazyUpdate(node, s, e);
    if (s > r || l > e) return 0;
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    return query(node * 2, s, m, l, r) | query(node * 2 + 1, m + 1, e, l, r);
}
 
void func() {
    char type;
    int l, r, k;
    while (K--) {
        cin >> type;
        if (type == 'C') {
            cin >> l >> r >> k;
            if (l > r) swap(l, r);
            update(11, N, l, r, k - 1);
        }
        else {
            cin >> l >> r;
            if (l > r) swap(l, r);
            int ret = query(11, N, l, r);
            int ans = 0;
            while (ret) {
                ans += (ret & 1);
                ret >>= 1;
            }
            cout << ans << '\n';
        }
    }
}
 
void input() {
    cin >> N >> M >> K;
    init(11, N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 1517 버블 소트  (0) 2024.06.16
boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 10167 금광  (0) 2022.09.02
boj 16993 연속합과 쿼리  (0) 2022.08.29
boj 12846 무서운 아르바이트  (0) 2022.08.19

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

 

10167번: 금광

첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이

www.acmicpc.net

이 문제를 풀기 전에, [boj 16993 연속합과 쿼리] 문제를 먼저 푸시는 것을 추천드립니다. [풀이]

 

금광을 풀기 위해 금광 세그가 등장하여 많이 알려진 것을 보면 얼마나 어려운 문제인지 예상이 될 것 같습니다.

금광세그 + 좌표압축 + 스위핑으로 많은 테크닉이 이 하나의 문제를 풀기 위해 필요합니다.

 

전체 흐름은

  1. 좌표압축으로 좌표 범위를 줄인 후에
  2. y 좌표를 기준으로 x 좌표들을 모으고
  3. y 좌표 범위를 이동시키며, 연속합의 최대를 구한다.

이렇게 되겠습니다.

 

좌표 압축

좌표를 인덱스로 하여 트리를 구성합니다.

좌표압축 설명은 [여기]에 포스팅되어 있습니다.

x, y 좌표 모두 압축 진행해주시면 됩니다.

y 좌표를 기준으로 x 좌표를 모을 예정이므로 다시 재정렬할 필요는 없습니다.

 

스위핑

먼저, y 좌표를 인덱스로 같은 y 좌표를 가지는 x 좌표를 벡터에 모읍니다.

yList[1] = {1, 2, 3} // y = 1인 x 좌표가 1, 2, 3

그 다음 y 좌표 범위를 이동하면서 최적의 답을 구합니다.

y 좌표의 범위는 1 ~ yCnt, 2 ~ yCnt, ..., y ~ yCnt에 존재하는 x 좌표들 대상입니다.

범위가 고정되었으니 이제 x 좌표들로 연속합의 최대를 구합니다.

 

금광세그

여기부터는 이제 연속합과 쿼리 문제와 동일합니다.

연속합의 최대를 구하기 위해 세그먼트 트리를 이용합니다.\

 

트리에는 아래 값들을 저장하게 됩니다.

  • l: leftNode의 최대
    • max(leftNode.l, leftNode.sum + rightNode.l)
  • r: rightNode의 최대
    • max(rightNode.r, rightNode.sum + leftNode.r)
  • max: 현재 노드의 최대
    • max(leftNode.max, rightNode.max, leftNode.r + rightNode.l)
  • sum: 현재 노드의 전체 합
    • leftNode.sum + rightNode.sum

y 좌표의 범위가 바뀔 때마다 들어오는 x 좌표 값들이 다르므로 트리는 반드시 초기화 해야합니다.

 

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 3001
using namespace std;
typedef long long ll;
typedef pair<intint> pii;
typedef pair<int, ll> pil;
 
typedef struct Point {
    int x, y;
    ll w;
    int idx;
}Point;
 
typedef struct Node {
    ll l, r, max, sum;
}Node;
 
Point list[MAX];
Node tree[MAX * 4];
vector<pil> yList[MAX];
int N;
 
void update(int node, int s, int e, int idx, ll diff) {
    if (idx < s || idx > e) return;
    if (s == e) {
        tree[node].l += diff;
        tree[node].r += diff;
        tree[node].max += diff;
        tree[node].sum += diff;
        return;
    }
 
    int m = (s + e) / 2;
    update(node * 2, s, m, idx, diff);
    update(node * 2 + 1, m + 1, e, idx, diff);
    tree[node] = { max(tree[node * 2].l, tree[node * 2].sum + tree[node * 2 + 1].l), max(tree[node * 2 + 1].r, tree[node * 2 + 1].sum + tree[node * 2].r), max(max(tree[node * 2].max, tree[node * 2 + 1].max), tree[node * 2].r + tree[node * 2 + 1].l), tree[node * 2].sum + tree[node * 2 + 1].sum };
}
 
Node query(int node, int s, int e, int l, int r) {
    if (s > r || l > e) return { (int)-1e9, (int)-1e9, (int)-1e90 };
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    Node leftNode = query(node * 2, s, m, l, r);
    Node rightNode = query(node * 2 + 1, m + 1, e, l, r);
    return { max(leftNode.l, leftNode.sum + rightNode.l), max(rightNode.r, rightNode.sum + leftNode.r), max(max(leftNode.max, rightNode.max), leftNode.r + rightNode.l), leftNode.sum + rightNode.sum };
}
 
void func() {
    sort(list + 1, list + 1 + N, [](Point a, Point b) {
        return a.x < b.x;
    });
 
    int pre = 1e9 + 1;
    int xCnt = 0;
    for (int i = 1; i <= N; i++) {
        if (pre != list[i].x) xCnt++;
        pre = list[i].x;
        list[i].x = xCnt;
    }
 
    sort(list + 1, list + 1 + N, [](Point a, Point b) {
        return a.y < b.y;
    });
 
    pre = 1e9 + 1;
    int yCnt = 0;
    for (int i = 1; i <= N; i++) {
        if (pre != list[i].y) yCnt++;
        pre = list[i].y;
        list[i].y = yCnt;
    }
 
    for (int i = 1; i <= N; i++) {
        yList[list[i].y].push_back({ list[i].x, list[i].w });
    }
 
    ll ans = -1e9 - 1;
    for (int i = 1; i <= yCnt; i++) {
        memset(tree, 0sizeof(tree));
        for (int j = i; j <= yCnt; j++) {
            for (int k = 0; k < yList[j].size(); k++) {
                update(11, N, yList[j][k].first, yList[j][k].second);
            }
            ans = max(ans, query(11, N, 1, N).max);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i].x >> list[i].y >> list[i].w;
        list[i].idx = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 12895 화려한 마을  (0) 2022.09.07
boj 16993 연속합과 쿼리  (0) 2022.08.29
boj 12846 무서운 아르바이트  (0) 2022.08.19
boj 1849 순열  (0) 2021.09.08

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

 

16993번: 연속합과 쿼리

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작

www.acmicpc.net

"금광 세그" 라고 불릴 정도의 웰노운 문제지만 어렵습니다. ㅠㅠ

이 문제는 "금광" 문제를 풀기 위한 워밍업 문제이며, 이 문제를 푸셨다면 금광 문제에 도전하시는 것도 좋습니다.

 

금광 세그는 구간에서 가장 큰 연속합을 구하는 문제입니다.

세그먼트 트리를 활용할 수 있으며, 두 개의 노드를 병합했을 때,

[왼쪽 노드의 최대, 오른쪽 노드의 최대, 두 노드의 중간]

이 정도가 답이 될 수 있습니다.

 

이를 구하기 위해 세그먼트 트리에는 다음과 같은 값을 저장합니다.

  • l: 왼쪽 하위노드 (leftNode)의 최대
  • r: 오른쪽 하위노드 (rightNode)의 최대
  • max: 현재 노드의 최대
  • sum: 현재 노드의 전체 합

이 값들을 구하는 방법은

  • l: max(leftNode.l, leftNode.sum + rightNode.l)
  • r: max(rightNode.r, rightNode.sum + leftNode.r)
  • max: max(leftNode.max, rightNode.max, leftNode.r + rightNode.l)
  • sum: leftNode.sum + rightNode.sum

이러면 전체 구간에서의 max를 구할 수 있습니다.

 

해당 식을 알고 있다면 쉽게 풀리는 문제지만, 처음보는 입장에서 이해하기는 어려웠습니다.

비슷한 문제로 update가 추가된 문제와 좌표압축이 추가된 금광 문제도 함께 공유드리고, 마무리하겠습니다.

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

 

15561번: 구간 합 최대? 2

첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 105,  - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. (-102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼리가

www.acmicpc.net

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

 

10167번: 금광

첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이

www.acmicpc.net

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
 
typedef struct Node {
    int l;
    int r;
    int max;
    int sum;
}Node;
 
Node tree[MAX * 4];
int list[MAX];
int N, M;
 
Node init(int node, int s, int e) {
    if (s == e) {
        return tree[node] = { list[s], list[s], list[s], list[s] };
    }
 
    int m = (s + e) / 2;
    Node leftNode = init(node * 2, s, m);
    Node rightNode = init(node * 2 + 1, m + 1, e);
    return tree[node] = { max(leftNode.l, leftNode.sum + rightNode.l), max(rightNode.r, leftNode.r + rightNode.sum), max(max(leftNode.max, rightNode.max), leftNode.r + rightNode.l), leftNode.sum + rightNode.sum };
}
 
Node query(int node, int s, int e, int l, int r) {
    if (s > r || l > e) return { (int)-1e9, (int)-1e9, (int)-1e90 };
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    Node leftNode = query(node * 2, s, m, l, r);
    Node rightNode = query(node * 2 + 1, m + 1, e, l, r);
    return { max(leftNode.l, leftNode.sum + rightNode.l), max(rightNode.r, leftNode.r + rightNode.sum), max(max(leftNode.max, rightNode.max), leftNode.r + rightNode.l), leftNode.sum + rightNode.sum };
}
 
void func() {
    int l, r;
    cin >> M;
    while (M--) {
        cin >> l >> r;
        cout << query(11, N, l, r).max << '\n';
    }
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    init(11, N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02
boj 12846 무서운 아르바이트  (0) 2022.08.19
boj 1849 순열  (0) 2021.09.08
boj 14719 빗물  (0) 2021.03.15

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

 

12846번: 무서운 아르바이트

성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다. 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다. 돈은 당일에 주지 않고 퇴직을 할 때 한

www.acmicpc.net

일을 연속적으로 해야하며, 한 번만 할 수 있습니다.

또한 일을 한 기간동안 가장 작은 일급 * 기간의 돈을 받습니다.

 

가장 작은 일급이 10이고, 5일동안 일해서 받은 50보다

가장 작은 일급이 20이고, 3일동안 일해서 받은 60이 더 많은 이익을 챙길 수 있습니다.

 

이 문제는 히스토그램 문제와 요구하는 것이 같으며,

https://emoney96.tistory.com/139

 

boj 6549 히스토그램에서 가장 큰 직사각형

www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주

emoney96.tistory.com

https://emoney96.tistory.com/138

 

boj 2104 부분배열 고르기

www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉,..

emoney96.tistory.com

두 문제와 동일한 풀이입니다.

 

트리에는 가장 작은 일급을 가진 인덱스를 저장합니다.

init 함수로 전 구간의 최소 인덱스를 저장합니다.

그리고 partition 함수를 통해 해당 구간에서 가장 작은 값을 가지는 인덱스를 query 함수로 찾은 후 최대 이익을 갱신합니다.

해당 인덱스는 가장 작은 값이므로 제외하고, [s ~ idx - 1] [idx + 1 ~ e] 구간으로 나누어서 같은 과정을 반복합니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
typedef long long ll;
 
ll tree[MAX * 4], list[MAX], ans;
int N;
 
void init(int node, int s, int e) {
    if (s == e) {
        tree[node] = s;
        return;
    }
 
    int m = (s + e) / 2;
    init(node * 2, s, m);
    init(node * 2 + 1, m + 1, e);
 
    int l = tree[node * 2];
    int r = tree[node * 2 + 1];
    if (list[l] < list[r]) tree[node] = l;
    else tree[node] = r;
 
    return;
}
 
int query(int node, int s, int e, int l, int r) {
    if (l > e || s > r) return -1;
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    int lIdx = query(node * 2, s, m, l, r);
    int rIdx = query(node * 2 + 1, m + 1, e, l, r);
 
    if (lIdx == -1) {
        return rIdx;
    }
    else if (rIdx == -1) {
        return lIdx;
    }
    else {
        return list[lIdx] < list[rIdx] ? lIdx : rIdx;
    }
}
 
void partition(int s, int e) {
    if (s > e) return;
 
    int idx = query(11, N, s, e);
    ans = max(ans, list[idx] * (ll)(e - s + 1));
    partition(s, idx - 1);
    partition(idx + 1, e);
}
 
void func() {
    init(11, N);
    partition(1, N);
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 10167 금광  (0) 2022.09.02
boj 16993 연속합과 쿼리  (0) 2022.08.29
boj 1849 순열  (0) 2021.09.08
boj 14719 빗물  (0) 2021.03.15
boj 2304 창고 다각형  (0) 2021.02.25

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

 

1849번: 순열

1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라

www.acmicpc.net

사탕 상자 문제와 비슷한 방법인 구간합을 이용하여 해결하였습니다.

https://emoney96.tistory.com/93 (사탕 상자 문제풀이)

 

먼저 1 ~ N 만큼의 리프노드가 모두 1로 이루어진 세그먼트 트리를 구합니다.

입력으로는 1 ~ N 까지 자신보다 왼쪽에 있는 수 중에 자신보다 큰 수의 갯수가 주어집니다.

 

가장 작은 숫자인 1부터 입력으로 주어진 자신보다 큰 수의 갯수 + 1이 되는 자리를 찾습니다.

만약 cnt[1] = 5면 1의 자리는 6이 됩니다.

자리를 찾게 되면 해당 자리의 리프노드의 값을 0으로 하고 구간 값도 갱신합니다.

이 과정을 반복한 후에 결과를 출력해주시면 됩니다.

 

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>
#define MAX 100000
using namespace std;
 
int list[MAX + 1], tree[(MAX + 1* 4];
int cnt[MAX + 1];
int N;
 
int init(int node, int s, int e) {
    if (s == e) {
        return tree[node] = 1;
    }
 
    int m = (s + e) / 2;
    return tree[node] = init(node * 2, s, m) + init(node * 2 + 1, m + 1, e);
}
 
void query(int node, int s, int e, int idx, int k) {
    if (s == e) {
        tree[node] = 0;
        list[s] = idx;
        return;
    }
 
    int m = (s + e) / 2;
    if (k <= tree[node * 2]) query(node * 2, s, m, idx, k);
    else query(node * 2 + 1, m + 1, e, idx, k - tree[node * 2]);
 
    tree[node] = tree[node * 2+ tree[node * 2 + 1];
}
 
void func() {
    for (int i = 1; i <= N; i++) {
        query(11, N, i, cnt[i] + 1);
    }
 
    for (int i = 1; i <= N; i++) {
        cout << list[i] << '\n';
    }
}
 
void input() {
    cin >> N;
    init(11, N);
    for (int i = 1; i <= N; i++) {
        cin >> cnt[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 16993 연속합과 쿼리  (0) 2022.08.29
boj 12846 무서운 아르바이트  (0) 2022.08.19
boj 14719 빗물  (0) 2021.03.15
boj 2304 창고 다각형  (0) 2021.02.25
boj 14438 수열과 쿼리 17  (0) 2021.02.21

www.acmicpc.net/problem/14719

 

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net

저는 2가지 방법으로 해결하였습니다.

 

하나는 그냥 구현으로, 다른 하나는 세그먼트 트리를 이용하였습니다.

 

먼저 블록의 최대 높이를 가진 인덱스(idx)를 구합니다.

그리고 왼쪽에서 idx까지, 오른쪽에서 idx까지 순회하면서 현재 최대 높이를 갱신해주고,

만약 현재 최대높이보다 블록의 높이가 더 작으면 그 차이만큼 더해주는 방식입니다.

 

 

emoney96.tistory.com/154

 

boj 2304 창고 다각형

www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는

emoney96.tistory.com

세그먼트 트리는 위의 문제와 같은 방식입니다.

 

트리에 각 높이의 최댓값을 저장합니다.

 

그 다음 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[501];
int N, M, maxheight, idx;
 
void func() {
    int ans = 0;
    int nowmax = 0;
    for (int i = 1; i <= idx; i++) {
        nowmax = max(nowmax, list[i]);
 
        if (nowmax > list[i]) {
            ans += (nowmax - list[i]);
        }
    }
 
    nowmax = 0;
    for (int i = N; i > idx; i--) {
        nowmax = max(nowmax, list[i]);
 
        if (nowmax > list[i]) {
            ans += (nowmax - list[i]);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
        if (maxheight < list[i]) {
            maxheight = list[i];
            idx = i;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

 

 

[세그먼트 트리]

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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[501], tree[2001];
int N, M;
 
int init(int node, int s, int e) {
    if (s == e) {
        return tree[node] = list[s];
    }
 
    int m = (s + e) / 2;
    return tree[node] = max(init(node * 2, s, m), init(node * 2 + 1, m + 1, e));
}
 
int query(int node, int s, int e, int l, int r) {
    if (l > e || s > r) return 0;
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    return max(query(node * 2, s, m, l, r), query(node * 2 + 1, m + 1, e, l, r));
}
 
void func() {
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int l = query(11, N, 1, i);
        int r = query(11, N, i + 1, N);
 
        int result = min(l, r);
 
        if (list[i] < result) {
            ans += result - list[i];
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    init(11, N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 12846 무서운 아르바이트  (0) 2022.08.19
boj 1849 순열  (0) 2021.09.08
boj 2304 창고 다각형  (0) 2021.02.25
boj 14438 수열과 쿼리 17  (0) 2021.02.21
boj 13537 수열과 쿼리 1  (0) 2021.02.21

www.acmicpc.net/problem/2304

 

2304번: 창고 다각형

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의

www.acmicpc.net

이 문제와 같은 문제를 코테에서 풀었지만 삽질을 하는바람에 시간없어서 못푼 문제입니다.. ㅠ 문제보자마자 바로 생각이 나더군요...

 

그때 접근했던 풀이방법이 떠올라서 그대로 구현해보니 AC를 받았습니다. 하..

방법은 세그먼트 트리입니다.

우선 위치인 l과 높이인 h를 입력으로 받습니다.

list배열에는 인덱스가 l인 기둥의 높이를 h로 유지합니다.

입력을 받는동안 L에 최대 인덱스를 갱신하고, 트리에 구간 최댓값을 유지합니다.

 

이제 func함수에서 1 ~ L까지 높이를 구합니다.

i번째 기둥의 최종 높이는 1 ~ i의 최댓값과 i ~ L의 최댓값 중 최솟값입니다.

이 값을 list[i]에 다시 넣어줍니다.

출력은 list의 누적합(1 ~ L까지)을 출력해주시면 됩니다.

 

 

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
 
#include <iostream>
#include <algorithm>
using namespace std;
 
int tree[4004], list[1001];
int N, L, ans;
 
int init(int node, int s, int e) {
    if (s == e) return tree[node] = list[s];
 
    int m = (s + e) / 2;
    return tree[node] = max(init(node * 2, s, m), init(node * 2 + 1, m + 1, e));
}
 
int query(int node, int s, int e, int l, int r) {
    if (l > e || s > r) return 0;
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    return max(query(node * 2, s, m, l, r), query(node * 2 + 1, m + 1, e, l, r));
}
 
void func() {
    for (int i = 1; i <= L; i++) {
        int l = query(11, L, 1, i);
        int r = query(11, L, i, L);
 
        list[i] = min(l, r);
 
        ans += list[i];
    }
 
    cout << ans << '\n';
}
 
void input() {
    int l, h;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> l >> h;
        list[l] = h;
        L = max(L, l);
    }
    init(11, L);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 1849 순열  (0) 2021.09.08
boj 14719 빗물  (0) 2021.03.15
boj 14438 수열과 쿼리 17  (0) 2021.02.21
boj 13537 수열과 쿼리 1  (0) 2021.02.21
boj 6549 히스토그램에서 가장 큰 직사각형  (0) 2021.02.19

www.acmicpc.net/problem/14438

 

14438번: 수열과 쿼리 17

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을

www.acmicpc.net

1 i v -> i번째 수를 v로 바꿉니다.

2 i j -> i ~ j 번째 수들 중에서 가장 작은 값을 출력합니다.

 

배열의 원소를 입력받을 때마다 세그먼트 트리로 최솟값을 갱신시켜줍니다.

 

그리고 쿼리를 입력받습니다.

1이면 i번째 수를 v로 바꾸는 update,

2이면 i ~ j번째 수들 중 가장 작은 값을 출력하는 query를 실행시킵니다.

현재 구간[s, e]이 찾으려는 구간[l, r]의 밖에 있으면 INF를 리턴,

완전히 포함되어있으면 tree[node]를 리턴합니다.

 

 

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
#include <iostream>
#include <algorithm>
#define INF 2147483647
using namespace std;
 
int tree[400004];
int N, M;
 
int update(int node, int s, int e, int idx, int diff) {
    if (idx < s || idx > e) return tree[node];
    if (s == e) return tree[node] = diff;
 
    int m = (s + e) / 2;
    return tree[node] = min(update(node * 2, s, m, idx, diff), update(node * 2 + 1, m + 1, e, idx, diff));
}
 
int query(int node, int s, int e, int l, int r) {
    if (l <= s && e <= r) return tree[node];
    if (l > e || r < s) return INF;
 
    int m = (s + e) / 2;
    return min(query(node * 2, s, m, l, r), query(node * 2 + 1, m + 1, e, l, r));
}
 
void func() {
    int type, a, b;
    cin >> M;
    while (M--) {
        cin >> type >> a >> b;
        if (type == 1) {
            update(11, N, a, b);
        }
        else {
            cout << query(11, N, a, b) << '\n';
        }
    }
}
 
void input() {
    int x;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> x;
        update(11, N, i, x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 14719 빗물  (0) 2021.03.15
boj 2304 창고 다각형  (0) 2021.02.25
boj 13537 수열과 쿼리 1  (0) 2021.02.21
boj 6549 히스토그램에서 가장 큰 직사각형  (0) 2021.02.19
boj 2104 부분배열 고르기  (0) 2021.02.19

+ Recent posts