'PS) BOJ/Segment Tree' 카테고리의 글 목록

전형적인 세그먼트 트리 문제인데 함정은 쿼리에 무조건 작은수~큰수라는 조건이 없으므로
조건으로 잘 처리해주면 금방 풀수 있는 문제이다.
바텀업 세그먼트 트리를 구현해서 풀었다.

구간합 구하기 문제는 역시 세그먼트 트리 구현해서 푸는게 짱인거같다...
(내가 아는선에서는... ㅎ)

시간복잡도는 M*NlogN 만큼 소요되는것같다.
주어지는 쿼리의 수가 10만턴정도이니 입출력을 줄여주는것도 시간을 충분히 줄여준다.

참고로 덧셈과정에서 정수형을 넘어갈수 있으니 long long을 사용했다.

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

1275번: 커피숍2

1275번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 커피숍2 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 2852 596 419 19.886% 문제 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.) 어느날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다. 그 게임은 다음과 같은 규칙을 갖는다. N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은

www.acmicpc.net

<CODE>

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
//pda_pro12
#include<algorithm>
#include<iostream>
 
#define N_ 100000
#define INT 0x7fff0000
 
using namespace std; 
 
typedef long long ll;
ll a[N_], seg[N_ * 4], n, q; 
 
void init(int node, int x, int y) {
    if (x == y) {
        seg[node] = a[x]; 
        return; 
    }
    int mid = (x + y) >> 1; 
    init(node << 1, x, mid); 
    init((node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1];
    return; 
}
 
void update(int pos, int val, int node, int x, int y) {
    if (pos < x || pos > y) return; 
    if (x==y) {
        seg[node] = val; 
        return; 
    }
    ll mid = (x + y) >> 1; 
    update(pos, val, node << 1, x, mid); 
    update(pos, val, (node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1]; 
    return; 
}
 
ll query(int lo, int hi, int node, int x, int y) {
    if (lo > y || hi < x) return 0; 
    if (lo <= x && y <= hi) return seg[node]; 
    ll mid = (x + y) >> 1; 
    ll l = query(lo, hi, node << 1, x, mid); 
    ll r = query(lo, hi, (node << 1) + 1, mid + 1, y);
    return l+r; 
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
 
    cin >> n >> q; 
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init(1, 1, n); 
    while (q--) {
        int a, b, c, d; 
        cin >> a >> b >> c >> d;
        int a1 = (a > b) ? b : a; int b1 = (a > b) ? a : b; 
        cout << query(a1, b1, 1, 1, n) << '\n'; 
        update(c, d, 1, 1, n);
    }
    return 0; 
}

저작자표시

'PS) BOJ > Segment Tree' 카테고리의 다른 글

[C++] 커피숍2 [백준 1275] (0)	2018.08.16
[C++]음주 코딩[백준 5676] (0)	2018.08.16

전형적인 세그먼트 트리 문제인데 함정은 쿼리에 무조건 작은수~큰수라는 조건이 없으므로
조건으로 잘 처리해주면 금방 풀수 있는 문제이다.
바텀업 세그먼트 트리를 구현해서 풀었다.

구간합 구하기 문제는 역시 세그먼트 트리 구현해서 푸는게 짱인거같다...
(내가 아는선에서는... ㅎ)

시간복잡도는 M*NlogN 만큼 소요되는것같다.
주어지는 쿼리의 수가 10만턴정도이니 입출력을 줄여주는것도 시간을 충분히 줄여준다.

참고로 덧셈과정에서 정수형을 넘어갈수 있으니 long long을 사용했다.

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

1275번: 커피숍2

1275번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 커피숍2 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 2852 596 419 19.886% 문제 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.) 어느날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다. 그 게임은 다음과 같은 규칙을 갖는다. N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은

www.acmicpc.net

<Code>

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
//pda_pro12
#include<algorithm>
#include<iostream>
 
#define N_ 100000
#define INT 0x7fff0000
 
using namespace std; 
 
typedef long long ll;
ll a[N_], seg[N_ * 4], n, q; 
 
void init(int node, int x, int y) {
    if (x == y) {
        seg[node] = a[x]; 
        return; 
    }
    int mid = (x + y) >> 1; 
    init(node << 1, x, mid); 
    init((node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1];
    return; 
}
 
void update(int pos, int val, int node, int x, int y) {
    if (pos < x || pos > y) return; 
    if (x==y) {
        seg[node] = val; 
        return; 
    }
    ll mid = (x + y) >> 1; 
    update(pos, val, node << 1, x, mid); 
    update(pos, val, (node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1]; 
    return; 
}
 
ll query(int lo, int hi, int node, int x, int y) {
    if (lo > y || hi < x) return 0; 
    if (lo <= x && y <= hi) return seg[node]; 
    ll mid = (x + y) >> 1; 
    ll l = query(lo, hi, node << 1, x, mid); 
    ll r = query(lo, hi, (node << 1) + 1, mid + 1, y);
    return l+r; 
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
 
    cin >> n >> q; 
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init(1, 1, n); 
    while (q--) {
        int a, b, c, d; 
        cin >> a >> b >> c >> d;
        int a1 = (a > b) ? b : a; int b1 = (a > b) ? a : b; 
        cout << query(a1, b1, 1, 1, n) << '\n'; 
        update(c, d, 1, 1, n);
    }
    return 0; 
}

저작자표시

'PS) BOJ > Segment Tree' 카테고리의 다른 글

[C++] 커피숍2 [백준 1275] (0)	2018.08.17
[C++]음주 코딩[백준 5676] (0)	2018.08.16

인덱스 범위가 10만이고 인덱스마다 값의 범위는 -100~100인 배열을 입력으로 주고,

구간을 갱신, 합산출을 M만큼 해주는건데 K의 범위또한 10만이다.

(즉, -> Prefix_Sum을 사용하거나 세그먼트를 써야한다는건데 갱신이 있으므로 세그먼트를 썻다.)

시간복잡도는 대략 O(KlogN) 인것 같다.

구현한 세그먼트는 바텀-업 세그먼트를 사용하였다

처음 풀때 실수 했던게 10만개의 인덱스가 전부 100을 갖고 있을때는 곱셈연산이므로

100의 10만승이라는 1Googol을 훌쩍 넘어버리는.. 수가 발생한다는 것을 뒤늦게 알고,

( 참고로 1구골이 10의 100승이다 )

세그트리를 구축해주는 함수에서 음, 양, 0을 판별하고 부분곱 방식으로 트리를 쌓아올렸다.

그래도 실행시간은 나쁘지 않게 나와서 좀 만족스럽다 ㅎㅎㅎ

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

5676번: 음주 코딩

문제 오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다. 상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다. 먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X 1 , X 2 , ... X N 을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다. 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다. 곱셈: 선영이는 상근이에게 i와 j를

www.acmicpc.net

<Code>

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
// pda_pro12
#include<algorithm>
#include<iostream>
#define N_ 100001   // 수열의 최대 크기 
#define INT 0x7fff0000
 
using namespace std; 
 
typedef long long ll; 
int seg[N_ * 4], a[N_], t, n, m, k;
 
void init(int node, int x, int y) {
    if (x == y) {
        if (a[x] > 0) seg[node] = 1; 
        else if (a[x] == 0) seg[node] = 0; 
        else if (a[x] < 0)  seg[node] = -1; 
        return; 
    }
    int mid = (x + y) >> 1; 
    init(node << 1, x, mid); 
    init((node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] * (seg[(node << 1) + 1]); 
    return; 
}
 
void update(int pos, int val, int node, int x, int y) { 
    if (pos < x || pos > y) return; 
    if (x == y) {
        if (val > 0) seg[node] = 1;
        else if (!val) seg[node] = 0; 
        else if (val < 0) seg[node] = -1; 
        return; 
    }
    int mid = (x + y) >> 1; 
    update(pos, val, node << 1, x, mid); 
    update(pos, val, (node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] * seg[(node << 1) + 1]; 
    return; 
}
 
int query(int lo, int hi, int node, int x, int y) {
    if (lo > y || x > hi) return 1; 
    if (lo <= x && y <= hi) return seg[node]; 
    int mid = (x + y) >> 1; 
    int l = query(lo, hi, node << 1, x, mid); 
    int r = query(lo, hi, (node << 1) + 1, mid + 1, y); 
    return l*r; 
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
    
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++)
            cin >> a[i]; 
 
        init(1, 1, n); 
        while (m--) {
            char inp; int x, y; 
            cin >> inp >> x >> y;
            if (inp == 'C') 
                update(x, y, 1, 1, n);
            else if (inp == 'P'){
                int ans = query(x, y, 1, 1, n);
                if (ans == 0)
                    cout << '0';
                else if (ans > 0)
                    cout << '+';
                else if ( ans < 0)
                    cout << '-'; 
            }
        }
        cout << '\n'; 
    }
    return 0; 
}

저작자표시

'PS) BOJ > Segment Tree' 카테고리의 다른 글

[C++] 커피숍2 [백준 1275] (0)	2018.08.17
[C++] 커피숍2 [백준 1275] (0)	2018.08.16

분명히 맞았는데 틀려서 들려보는 블로그