백준/세그먼트 트리 (27) 썸네일형 리스트형 백준 16978 - 수열과 쿼리 22 https://www.acmicpc.net/problem/16978 힌트 더보기 x번째 원소 갱신을 하기 전 x - 1번째 원소 갱신을 한 세그먼트 트리의 구간합을 구할 수 있다. 각 쿼리를 보존하여 적절한 시기에 처리하도록 한다. 풀이 더보기 특정 시점까지 갱신이 적용되었을 때의 구간 합을 구하는 문제이다. 조금만 생각해보면 구간 합은 원소의 갱신에 미치는 영향이 없다는 사실을 깨달을 수 있다. 그렇다면 0번째 원소 갱신을 수행 후 구간 합 연산 -> 1번째 원소 갱신 수행 -> 1번째 원소 갱신을 수행 후 구간 합 연산 -> 2번째 원소 갱신 수행 ->... 이처럼 계산하면 질의마다 올바른 값을 얻을 수 있다. 그런데 어떻게 구현해야 될까? 세그먼트 트리를 초기화만 해주고 입력받는 쿼리들에 대해 바로.. 백준 1615 - 교차개수세기 https://www.acmicpc.net/problem/1615 힌트 더보기 이 문제를 풀기 위해선 inversion counting에 대한 지식이 있어야 한다. 문제에 주어진 형태처럼 교차 그래프가 주어졌을 때의 LIS 문제를 풀어본 경험이 있다면 이것도 비슷하게 접근할 수 있다. 생각해보자! 풀이 더보기 교차 그래프가 주어지고 몇개의 간선이 교차하는지 알아내야 한다. 어느 쪽 노드 집합을 기준으로 정렬을 한 후 반대 쪽 노드 집합들의 나열 형태를 보면서 교차 간선의 개수를 세보자. 그러면 inversion counting의 형태를 띄는 것을 관찰할 수 있다. 자세한 설명은 동일한 유형의 문제 풀이를 참조하라. 그대로 inversion counting의 개수를 출력해주면 된다. 전체 코드 #pragm.. 백준 12844 - XOR https://www.acmicpc.net/problem/12844 힌트 1 더보기 세그먼트 트리의 lazy propagation을 이용하여 특정 구간에 대한 연산을 $O(logN)$ 시간 복잡도로 적용할 수 있다. 힌트2 더보기 xor의 연산 기호가 $\oplus$이고 임의의 원소 A에 대해 $A \oplus A = 0$ $A \oplus 0 = A$ 이다. 이 성질을 lazy propagation에 적용할 수 있는가? 풀이 더보기 1번 쿼리를 보면 lazy propagation을 응용해야 하는 것을 알 수 있다. xor 연산을 어떻게 적용할까? xor의 두 성질을 짚고 가자. $A \oplus A = 0$ $A \oplus 0 = A$ 이 성질을 통해 같은 수를 홀수 번 xor하면 A, 짝수 번 xo.. 백준 1280 - 나무 심기 https://www.acmicpc.net/problem/1280 힌트 1 더보기 특정 구간에 존재하는 나무의 개수와 위치의 합을 보존한다. 특정 구간에 존재하는 나무의 개수를 활용해서 이전에 심어진 나무와의 거리 합을 빠르게 구하는 방법을 생각해본다. 힌트 2 더보기 i를 이전에 심은 나무의 index, X는 현재 나무를 심을 index라고 하자. 심을 나무와 심어진 나무들의 거리 합은 다음 식으로 표현할 수 있다. $sum = \sum_{i = 1}^{X - 1}|tree_i - tree_X|$ 해당 식은 다음과 같이 바꿀 수 있다. $sum = |\sum_{i = 1}^{X - 1}tree_i - \sum_{i = 1}^{X - 1}tree_X|$ 이 식을 구현할 방법을 생각해본다. 풀이 더보기 i.. 백준 13537 - 수열과 쿼리 1 https://www.acmicpc.net/problem/13537 힌트 1 더보기 수열의 원소를 바꾸는 연산은 없다. 힌트 2 더보기 수열의 갱신이 없는 상태에서 특정 구간의 원소 index를 빠르게 찾기 위해 Merge Sort Tree를 이용할 수 있다. 풀이 수열이 주어지고 특정 구간에서 k보다 큰 원소를 찾는 연산을 최대 10만 번 수행한다. 따라서 해당 연산을 빠르게 수행할 필요가 있고, Merge Sort Tree가 이를 가능케 한다. 머지 소트 트리를 구현해서 k보다 큰 원소가 나타나는 index를 upper bound로 찾으면 특정 구간에서 k 이하 원소의 개수를 확보할 수 있다. 우리는 k보다 큰 원소의 갯수를 알고 싶으므로 (구간의 길이 - 머지 소트 트리의 질의로 찾은 k 이하 원소.. 이전 1 2 3 4 5 6 다음
