백준/세그먼트 트리 (27) 썸네일형 리스트형 [ICPC] 백준 1849 - 순열 https://www.acmicpc.net/problem/1849 번역은 너무 간단히 쓰여 있어서 원문을 보는게 문제 이해를 더 쉽게 할 수 있을지도 모른다. 문제 설명 주어진 숫자들을 배열 A라고 했을 때 A[i]는 배열의 0 ~ i - 1 index에서 자기보다 큰 숫자가 출현한 횟수를 나타낸다. 이 정보를 기반으로 원래의 순열을 복원하라. 풀이 1부터 N까지 차례대로 순열을 복원한다고 했을 때 "해당 숫자가 위치하는 곳 왼쪽에서 채워지지 않은 index가 몇개가 되는가?"로 추적하여 복원을 할 수 있다. 그러면 세그먼트 트리를 이용하여 순열이 채워지지 않은 index는 1로 하여 트리를 초기화 할 수 있다. 그러면 현재 구간에서 비어있는 index의 개수를 구해 숫자가 들어갈 알맞는 위치를 찾는 질.. 백준 2263 - 사탕상자 https://www.acmicpc.net/problem/2243 특정 맛을 가진 사탕의 개수를 변경하거나 k번째로 맛있는 사탕을 꺼내야 하는 질의를 최대 10만개 수행해야 한다. 세그먼트 트리를 통해 각 맛의 정도에 해당하는 사탕의 개수를 세그먼트 트리로 관리하면서 k번째로 맛있는 사탕(이하 k번째 사탕)을 추적하는 질의를 작성하면 된다. 맛의 정도를 index로 하여 배열을 구성하면 update는 구간합 용도로 구현한 세그먼트 트리의 그것과 동일하게 작성이 가능하다. k번째 사탕을 추적하는 질의는 현재 노드에서 왼쪽 구간의 사탕 개수와 오른쪽 구간의 사탕 개수를 비교한다. 만약 k보다 왼쪽 구간의 개수 이상이면 왼쪽 노드, 그렇지 않으면 오른쪽 노드로 가지치기 하여 로그 스케일로 줄여나가 원하는 사탕.. 백준 12837 - 가계부 (Hard) https://www.acmicpc.net/problem/12837 가계부에 내용이 계속 변하고 $10^{5}$개의 질의를 처리해야 하므로 세그먼트 트리를 사용한다. 수입, 지출이 바뀌는 것이 아니라 추가되는 것이므로 갱신 연산을 수행할 때 이에 유의하도록 한다. 전체 코드 더보기 #include using namespace std; using ll = long long; int n, q; ll ar[1000001]; inline int mid(int stt, int end) { return stt + (end - stt) / 2; } void update(vector &tree, int node, int start, int end, int idx, ll diff) { if (idx > end || id.. 백준 14438 - 수열과 쿼리 17 https://www.acmicpc.net/problem/14438 배열의 값을 바꾸고 특정 구간의 최솟값을 물어보는 질의가 최대 10만건 들어온다. 세그먼트 트리를 통해 구간의 최솟값을 빠르게 계산하면 된다. 구간의 최솟값을 구할 때 구간을 벗어나는 범위는 INF로 처리해주면 된다. 전체 코드 더보기 #include using namespace std; int ar[100001]; int n; inline int mid(int stt, int end) { return stt + (end - stt) / 2; } int init(vector &tree, int node, int start, int end) { if (start == end) return tree[node] = ar[start]; int .. [ICPC] 백준 5676 - 음주 코딩 https://www.acmicpc.net/problem/5676 풀이 세트당 최대 10만개의 질의를 통해 구간 곱을 구하고 갱신하는 문제이다. 이를 처리하기 위해 세그먼트 트리를 생각해볼 수 있다. 다만 갱신하려는 구간에 0이 있는 경우 구간의 곱은 0이 되어 갱신할 때 어려움을 겪을 수 있다. 구간을 갱신할 때 먼저 리프 노드의 값을 바꿔주고 부모 노드에 이를 반영해주도록 하면 0이 포함된 구간은 문제 없이 처리할 수 있다. 문제에서는 값의 부호만 중요하므로 혹시 모를 오버플로우를 방지하기 위해 양수는 1, 음수는 -1로 통일하여 계산하도록 한다. 문제에서 요구하는 대로 출력하면 된다. 전체 코드 더보기 #include using namespace std; int ar[100001]; int n, k.. 이전 1 2 3 4 5 6 다음
