반응형

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

 

13544번: 수열과 쿼리 3

길이가 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. a, b, c를 입력받고 pre에 xor 한 후 그 값을 이용하여 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

3. ans를 출력하고, pre에 ans를 저장한 후 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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
int pre;
 
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, 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 (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
    else {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
}
 
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 (s > j || e < i) 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;
 
    while (M--) {
        int a, b, c;
        cin >> a >> b >> c;
 
        ans = 0;
 
        a ^= pre;
        b ^= pre;
        c ^= pre;
 
        getTree(1, 1, N, a, b, c);
 
        cout << ans << '\n';
 
        pre = ans;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
반응형

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

 

12016번: 라운드 로빈 스케줄러

첫째 줄에 작업의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 각 작업을 수행해야하는 시간이 공백으로 구분되어 주어진다. 각 작업을 수행해야하는 시간은 1보다 크거나 같고, 1,000,000,000보다

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. 작업의 각 번호의 값을 1로 대입해 Segment Tree를 채웁니다.

 

2. 작업 수행 시간을 입력받고, 작업 수행 시간을 기준으로 오름차순으로, 작업의 번호를 기준으로 내림차순으로 정렬합니다.

 

3. 현재까지 작업한 작업의 개수를 Cur에 저장하고, 현재 같은 작업수를 가진 작업들의 수를 cnt, 현재 같은 작업수를 가진 작업들과 이전의 같은 작업수를 가진 작업들과의 차를 cur에 저장하고, 현재 남아있는 작업의 개수를 Cnt에 저장합니다.

 

4. 이전 작업의 수행 시간과 현재 작업의 수행 시간이 같다면 cnt++를 수행하고, 해당 작업 번호의 segment tree 노드의 값을 -1 해주고, ans[ arr[ i ].second ] = Cur + getTree(N, N + arr[ i ].second - 1) + cur * Cnt 의 식을 이용하여 ans배열을 채웁니다.

 

5. 이전 작업의 수행 시간과 현재 작업의 수행 시간이 다르다면

Cur += Cnt * (cur + 1);
Cnt -= cnt;
cnt = 0;
cur = arr[ i ].first - arr[ i - 1 ].first - 1;
temp = arr[ i ].first;
i--;

를 수행해줍니다.

 

6. 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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int N;
int segTree[200000];
pair<int, int> arr[100001];
ll ans[100001];
 
bool cmp(pair<int, int> left, pair<int, int> right)
{
    if (left.first == right.first) return left.second > right.second;
    return left.first < right.first;
}
 
void updateTree(int idx, int diff)
{
    while (idx) {
        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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        updateTree(N + i - 1, 1);
        cin >> arr[i].first;
        arr[i].second = i;
    }
 
    sort(arr + 1, arr + N + 1, cmp);
 
    int temp = arr[1].first;
    int cnt = 0;
    int Cnt = N;
    int cur = arr[1].first - 1;
    ll Cur = 0;
 
    for (int i = 1; i <= N; i++) {
        if (temp == arr[i].first) {
            cnt++;
            ans[arr[i].second] = Cur + (ll)getTree(N, N + arr[i].second - 1) + 1LL * cur * Cnt;
            updateTree(N + arr[i].second - 1, -1);
        }
        else {
            Cur += 1LL * Cnt * (1LL * cur + 1);
            Cnt -= cnt;
            cnt = 0;
            cur = arr[i].first - arr[i - 1].first - 1;
            temp = arr[i].first;
            i--;
        }
    }
 
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
반응형

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/2465

 

2465번: 줄 세우기

첫째 줄에는 전체 사람의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에 사람들의 키를 나타내는 양의 정수가 하나씩 주어진다. 여기서 모든 키들은 2×109이하이다. 그리고 마지막 줄에 수열

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 키를 입력받고, map 자료구조를 활용해 각 키의 개수를 저장합니다.

 

2. 입력받은 키를 오름차순으로 정렬해 vector에 저장합니다.

 

3. vector의 인덱스를 기준으로 segment tree를 만듭니다.

 

4. 키의 순서를 N번째부터 1번째까지 돌면서 현재 남아있는 키 중에서 해당 정수 + 1만큼의 값을 가지고 있는 수를 ans 배열에 추가합니다.

 

5. ans 배열을 N번부터 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
#include<iostream>
#include<set>
#include<unordered_map>
#include<vector>
 
using namespace std;
 
int N;
int segTree[262222];
unordered_map<int, int> m;
set<int> se;
vector<int> arr;
vector<int> ans;
int seq[100000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] += m[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 updateTree(int node, int s, int e, int idx)
{
    segTree[node]--;
    if (s == e) {
        ans.push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    if (segTree[node * 2] >= idx) {
        updateTree(node * 2, s, m, idx);
    }
    else {
        updateTree(node * 2 + 1, m + 1, e, idx - segTree[node * 2]);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        se.insert(n);
        m[n]++;
    }
    
    arr.push_back(-1);
 
    for (auto& next : se) {
        arr.push_back(next);
    }
 
    makeTree(1, 1, arr.size() - 1);
 
    for (int i = 0; i < N; i++) {
        cin >> seq[i];
    }
 
    for (int i = N - 1; i >= 0; i--) {
        updateTree(1, 1, arr.size() - 1, seq[i] + 1);
    }
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
반응형

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

 

5012번: 불만 정렬

정렬 알고리즘의 상한(upper bound)은 n2이다. 이 사실은 쉽게 증명할 수 있다. 올바른 순서가 아닌 임의의 두 원소(ai > aj, i < j)를 선택하고, 그 위치를 서로 바꿔준다. 이렇게 올바른 순서가 아닌 것

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. arr배열에 수열을 입력받고, 0부터 n-1번까지 for문을 통해 돌면서 자신보다 큰 값을 gop에 저장합니다.

 

2. n-1부터 0까지 for문을 통해 돌면서 자신보다 작은 값을  gop에 곱합니다.

 

3. ans에 모든 gop의 값을 더한 후 출력합니다.

 

[ 소스코드 ]

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;
int segTree[200000];
int arr[100000];
ll gop[100000];
ll ans;
 
void updateTree(int idx)
{
    while (idx) {
        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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        gop[i] = getTree(n + arr[i], 2 * n - 1);
        updateTree(n + arr[i] - 1);
    }
 
    fill(segTree, segTree + 2 * n, 0);
 
    for (int i = n - 1; i >= 0; i--) {
        gop[i] *= getTree(n, n + arr[i] - 2);
        updateTree(n + arr[i] - 1);
        ans += gop[i];
    }
    
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
반응형

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

 

17408번: 수열과 쿼리 24

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i < j ≤ r을 만족하는 모든 Ai + Aj 중에서

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 세그먼트 트리의 노드에 구간의 최댓값과 인덱스를 저장해 줍니다.

 

2. l부터 r까지의 인덱스 중 최댓값의 인덱스를 저장하고, l 부터 인덱스까지 와 인덱스 + 1 부터 r 까지의 값과 l부터 인덱스 -1 까지와 인덱스부터 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
#include<iostream>
 
using namespace std;
 
int N, M;
pair<int,int> segTree[262222];
int arr[100001];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = { arr[s], s};
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    if (segTree[node*2].first > segTree[node*2+1].first) {
        segTree[node] = segTree[node * 2];
    }
    else {
        segTree[node] = segTree[node * 2 + 1];
    }
}
 
void updateTree(int node, int s, int e, int idx, int v)
{
    if (idx < s || e < idx) return;
    if (s == e) {
        segTree[node].first = v;
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, idx, v);
    updateTree(node * 2 + 1, m + 1, e, idx, v);
 
    if (segTree[node * 2].first > segTree[node * 2 + 1].first) {
        segTree[node] = segTree[node * 2];
    }
    else {
        segTree[node] = segTree[node * 2 + 1];
    }
}
 
pair<int,int> getTree(int node, int s, int e, int sidx, int eidx)
{
    if (e < sidx || s > eidx) return { 0,0 };
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    pair<int, int> left = getTree(node * 2, s, m, sidx, eidx);
    pair<int, int> right = getTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    if (left.first > right.first) {
        return left;
    }
    else {
        return right;
    }
}
 
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 t = 0; t < M; t++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int i, v;
            cin >> i >> v;
            updateTree(1, 1, N, i, v);
        }
        else {
            int l, r;
            cin >> l >> r;
            int idx = getTree(1, 1, N, l, r).second;
 
            int ans = max(getTree(1, 1, N, l, idx).first + getTree(1, 1, N, idx + 1, r).first, getTree(1, 1, N, l, idx - 1).first + getTree(1, 1, N, idx, r).first);
            cout << ans << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
반응형

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

 

14459번: 소가 길을 건너간 이유 11

우리는 존의 고민을 해결해 줄 방법을 찾았지만, 그걸 알려 주러 가다가 길을 잃었다. 존의 농장에 가긴 했지만, 2N개의 목초지는 없고 웬 N×N 격자가 있는 것이다. 알고 보니 우리는 동명이인의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. a 배열을 만들어 왼쪽 소들의 종 번호의 인덱스를 저장하고, b 배열을 만들어 오른쪽 소들의 종 번호의 인덱스를 저장합니다.

 

2. 이중 for문을 이용하여 절댓값의 차이가 4 이하인 쌍을 vector<pair<int,int>>에 저장합니다.

 

3. 이 때 first의 값을 기준으로 오름차순, second의 값을 기준으로 내림차순으로 정렬합니다.

 

4. lower_bound를 이용하여 LIS를 만들어 주고, LIS의 길이를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int a[100001];
int b[100001];
vector<pair<int, int>> arr;
 
bool cmp(pair<int, int> left, pair<int, int> right) 
{
    if (left.first == right.first) return left.second > right.second;
    return left.first < right.first;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        a[n] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        b[n] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = max(1, i - 4); j <= min(N, i + 4); j++) {
            arr.push_back({ a[i], b[j] });
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    vector<int>lis;
 
    for (auto& next : arr) {
        if (lis.empty()) {
            lis.push_back(next.second);
        }
        else {
            auto it = lower_bound(lis.begin(), lis.end(), next.second);
            if (it == lis.end()) {
                lis.push_back(next.second);
            }
            else {
                *it = next.second;
            }
        }
    }
 
    cout << lis.size();
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
반응형

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

 

15967번: 에바쿰

재성이가 재혁이를 때린 날수 N과 재성이가 변덕을 부린 날의 개수 Q1, 재혁이가 얼마나 맞았는지 궁금한 구간의 개수 Q2가 주어진다. (1 ≤ N ≤ 1,000,000, 0 ≤ Q1, Q2 ≤ 10,000) 그 다음줄엔 재혁이가 i

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
#include<iostream>
#define ll long long
 
using namespace std;
 
ll segTree[2100000];
int lazy[2100000];
int N, Q1, Q2;
int arr[1000001];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node]) {
        segTree[node] += 1LL * lazy[node] * (1LL * e - s + 1);
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
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 updateTree(int node, int s, int e, int sidx, int eidx, int diff)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] += 1LL * diff * (1LL * e - s + 1);
        if (s != e) {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
    
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
ll getTree(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];
 
    int m = (s + e) / 2;
    ll left = getTree(node * 2, s, m, sidx, eidx);
    ll right = getTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q1 >> Q2;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q1 + Q2; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int n, m;
            cin >> n >> m;
            cout << getTree(1, 1, N, n, m) << '\n';
        }
        else {
            int s, e, l;
            cin >> s >> e >> l;
            updateTree(1, 1, N, s, e, l);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
[ 백준 ] 14852번 - 타일 채우기 3 (C++)  (0) 2023.07.30
반응형

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

 

16978번: 수열과 쿼리 22

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. arr배열에 수열을 입력받고, 비재귀세그먼트 트리를 이용하여 구간합을 구해줍니다.

 

2. cmd가 1인 쿼리와 2인 쿼리를 각각 저장하고, cmd가 2인 쿼리를 k를 기준으로 오름차순으로 정렬합니다.

 

3. 현재 상태에서 cmd가 1인 k번 쿼리까지 진행해 준 후, cmd가 2인 쿼리를 진행하고, 순서에 맞게 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
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
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct query2 {
    int k, i, j;
    int seq;
};
 
struct cmp {
    bool operator()(query2 left, query2 right) {
        return left.k < right.k;
    }
};
 
int N, M;
ll segTree[200000];
vector<pair<int, int>> query;
vector<query2> queryArr;
ll ans[100000];
int arr[100001];
 
void updateTree(int idx, int n)
{
    while (idx) {
        segTree[idx] += n;
        idx >>= 1;
    }
}
 
ll getTree(int l, int r)
{
    ll 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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        arr[i] = n;
        updateTree(N + i, n);
    }
 
    cin >> M;
    int cnt = 0;
 
    for (int i = 0; i < M; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int i, v;
            cin >> i >> v;
            query.push_back({ i,v });
        }
        else {
            int k, i, j;
            cin >> k >> i >> j;
            queryArr.push_back({ k,i,j,cnt++ });
        }
    }
 
    sort(queryArr.begin(), queryArr.end(), cmp());
 
    int cur = 0;
 
    for (auto& next : queryArr) {
        int k = next.k;
        for (int i = cur; i < k; i++) {
            int a = query[i].first;
            int b = query[i].second;
            updateTree(a + N - 1, b - arr[a-1]);
            arr[a - 1] = b;
        }
        cur = k;
 
        ans[next.seq] = getTree(N + next.i - 1, N + next.j - 1);
    }
 
    for (int i = 0; i < cnt; i++) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
[ 백준 ] 14852번 - 타일 채우기 3 (C++)  (0) 2023.07.30
[ 백준 ] 16954번 - 움직이는 미로 탈출 (C++)  (0) 2023.07.29
반응형

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

+ Recent posts

티스토리툴바