Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 후니의 쉽게 쓴 시스코 네트워킹
- Effective Java
- 알고리즘
- 백준
- dfs
- 백트래킹
- 그리디
- 세그먼트 트리
- swea
- 문자열
- 동적계획법
- Kotlin
- 스택
- 수학
- 완전탐색
- mst
- 이분탐색
- Network
- 구현
- java
- 투 포인터
- 에라토스테네스의 체
- 시뮬레이션
- 유니온 파인드
- JUnit 5
- 플로이드-와샬
- 프로그래머스
- CS
- 위상정렬
- BFS
Archives
반갑습니다!
[백준] 5676 음주 코딩 본문
풀이
세그먼트 트리를 사용해서 해결할 수 있다. 이 문제에서 일정 구간의 곱이 양수인지, 0인지, 음수인지가 중요한 것이기 때문에 입력받은 숫자를 1, 0, -1로 변환해서 저장해준 것을 유의하자. 그리고 쿼리를 처리할 때 idx가 범위를 벗어난 경우 곱셈의 항등원인 1을 리턴해 해결했다.
코드
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int n, k; | |
vector<int> num, tree; | |
int init(int node, int start, int end) { | |
if (start == end) return tree[node] = num[end]; | |
int mid = (start + end) / 2; | |
return tree[node] = init(2 * node, start, mid) * init(2 * node + 1, mid + 1, end); | |
} | |
int query(int node, int start, int end, int left, int right) { | |
if (start > right || end < left) return 1; | |
if (left <= start && end <= right) return tree[node]; | |
int mid = (start + end) / 2; | |
return query(2 * node, start, mid, left, right) * query(2 * node + 1, mid + 1, end, left, right); | |
} | |
void update(int node, int start, int end, int idx, int v) { | |
if (idx < start || idx > end) return; | |
if (start == end) { | |
tree[node] = v; | |
return; | |
} | |
if (start != end) { | |
int mid = (start + end) / 2; | |
update(2 * node, start, mid, idx, v); | |
update(2 * node + 1, mid + 1, end, idx, v); | |
tree[node] = tree[2 * node] * tree[2 * node + 1]; | |
} | |
} | |
int main() { | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
while (cin >> n >> k) { | |
num = vector<int>(n + 1); | |
tree = vector<int>(4 * (n + 1)); | |
for (int i = 1; i <= n; i++) { | |
int tmp; | |
cin >> tmp; | |
if (tmp > 0) num[i] = 1; | |
else if (tmp == 0) num[i] = 0; | |
else num[i] = -1; | |
} | |
init(1, 1, n); | |
while (k--) { | |
char c; | |
int i, v; | |
cin >> c >> i >> v; | |
if (c == 'C') { | |
if (v > 0) num[i] = 1; | |
else if (v == 0) num[i] = 0; | |
else num[i] = -1; | |
update(1, 1, n, i, num[i]); | |
} | |
else { | |
int result = query(1, 1, n, i, v); | |
if (result > 0) cout << "+"; | |
else if (result == 0) cout << "0"; | |
else cout << "-"; | |
} | |
} | |
cout << '\n'; | |
} | |
return 0; | |
} |
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 1213 팰린드롬 만들기 (0) | 2020.12.10 |
---|---|
[백준] 14438 수열과 쿼리 17 (0) | 2020.12.04 |
[백준] 2268 수들의 합 (0) | 2020.11.30 |
[백준] 1275 커피숍2 (0) | 2020.11.29 |
[백준] 10999 구간 합 구하기 2 (0) | 2020.11.29 |