[C/C++] 백준 5676번 - 음주 코딩
✏️ 문제 링크
https://www.acmicpc.net/problem/5676
5676번: 음주 코딩
각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.
www.acmicpc.net
✏️ 문제 설명
✏️ 문제 풀이
기본적인 세그먼트 트리 구현 문제입니다.
그냥 계산하시면 오버플로우가 발생할 수 있으니 양수일 때는 1, 0일때는 0, 음수일 때는 -1로 처리해줍니다!
✏️ 문제 코드
#include<iostream>
#include<vector>
using namespace std;
int N, K;
vector<int>arr, tree;
int l, r, index, value,a;
char query;
int initTree(int start, int end, int node);
int updateTree(int start, int end, int node, int index, int value);
int findSum(int start, int end, int node, int l, int r);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (cin >> N >> K) {
// 각 배열들 초기화 및 입력
arr.resize(N);
tree.resize(N * 4);
for (int i = 0; i < N; i++) {
cin >> a;
if (a > 0)
arr[i] = 1;
else if (a == 0)
arr[i] = 0;
else
arr[i] = -1;
}
// 세그먼트 트리 구현
initTree(0, N - 1, 1);
for (int i = 0; i < K; i++) {
cin >> query;
if (query == 'C') {
cin >> index >> value;
if (value > 0)
value = 1;
else if (value == 0)
value = 0;
else
value = -1;
updateTree(0, N - 1, 1, index - 1, value);
}
else {
cin >> l >> r;
int res = findSum(0, N - 1, 1, l - 1, r - 1);
if (res == 1)
cout << '+';
else if (res == 0)
cout << 0;
else
cout << '-';
}
}
cout << '\n';
}
}
int initTree(int start, int end, int node)
{
if (start == end)
return tree[node] = arr[start];
int mid = (start + end) / 2;
return tree[node] = initTree(start, mid, node * 2) * initTree(mid + 1, end, node * 2 + 1);
}
int updateTree(int start, int end, int node, int index, int value)
{
if (index<start || index>end)
return tree[node];
if(start==end)
return tree[node] = value;
int mid = (start + end) / 2;
return tree[node] = updateTree(start, mid, node * 2, index, value) * updateTree(mid + 1, end, node * 2 + 1, index, value);
}
int findSum(int start, int end, int node, int l, int r)
{
if (l > end || r < start)
return 1;
if (l <= start && end <= r)
return tree[node];
int mid = (start + end) / 2;
return findSum(start, mid, node * 2, l, r) * findSum(mid + 1, end, node * 2 + 1, l, r);
}
✏️ 더 많은 세그먼트 트리 문제 보기
https://pooreumjung.tistory.com/328
[C/C++] 백준 18436번 - 수열과 쿼리 37
✏️ 문제 링크 https://www.acmicpc.net/problem/18436 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤
pooreumjung.tistory.com
https://pooreumjung.tistory.com/313
[C/C++] 백준 - 수열과 쿼리 문제
백준 14438번 수열과 쿼리 17 https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼
pooreumjung.tistory.com
https://pooreumjung.tistory.com/312
[C/C++] 백준 - 세그먼트 트리 문제
✏️ 세그먼트 트리 기본 개념 https://pooreumjung.tistory.com/305 Algorithm 공부 #21 - 세그먼트 트리 Algorithm 공부 #21 - 세그먼트 트리 세그먼트 트리(Segmant Tree) ● 주어진 제이터의 구간 합과 데이트 업데
pooreumjung.tistory.com