세그먼트 트리 (21) 썸네일형 리스트형 백준 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 https://www.acmicpc.net/problem/17353 사전 지식 imos법을 알면 풀이를 쉽게 이해할 수 있다. 이 포스트에서는 imos법을 알고 있다는 가정 하에 설명하도록 한다. 공차가 1인 등차 수열 이 문제는 공차가 1인 등차수열을 구간에 더하면서 포인트 쿼리를 수행한다. 여기서 포인트 쿼리를 구간 쿼리로 바꿔보자. 점 x에 떨어진 별의 개수가 아닌 구간 [1, x]의 합을 구하는 쿼리로 바꾼다. 왜 이렇게 쿼리를 바꾸냐면 쿼리 1을 스위핑 덧셈 문제로 바꾸기 위함이다. 얘를 들어 다음 배열을 살펴보자. 1 2 3 4 5 이 배열의 원소들 $a_{1}, a_{2},... $을 $imos(i) - imos(0)$의 형태로 구하려면 어떻게 할까? 1 1 1 1 1 -5 이렇게 배열을 구.. 세그먼트 트리로 직사각형 스위핑 feat. 3392 화성 지도 우리는 몇몇 문제를 통해 세그먼트 트리와 스위핑으로 직사각형의 면적 혹은 둘레를 구하는 방법을 알아볼 것이다. 대표적인 문제는 화성 지도가 되겠다. https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net 스위핑 세그먼트 트리 소개 N개의 직사각형이 주어졌을 때 중복을 고려하여 총면적을 구하는 문제다. 바로 본론으로 들어가 우리는 두 개의 세그먼트 트리를 사용하겠다. 각 세그먼트 트리의 용.. 백준 1572 - 중앙값 https://www.acmicpc.net/problem/1572 전형적인 세그먼트 트리로 k번째 수를 찾는 쿼리를 이용하는 문제이다. 하지만 그 구현은 너무나도 귀찮다. C++을 사용하고 있다면 pbds를 이용해 간단하게 풀 수 있다. find_by_order와 order_by_key를 잘 이용하자. 전체 코드 더보기 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 #pragma GCC target("sse.. 백준 14287 - 회사 문화 3 참고 오일러 투어에 대해 모르면 여기를 먼저 보고 오자. 풀이 회사 문화 2와는 달리 더하는 방향이 반대이다. 어떻게 처리할 수 있을까? 일단 예제의 그래프를 그려보자. 여기서 정점 3에 3의 값을 더하면 1까지 3씩 더해야 한다. 하지만 단순히 간선 방향을 거꾸로만 하면 정점이 계속 중복 계산돼서 시간 초과 판정을 받고 방문 처리를 하면 사장까지 올라갈 수 없는 경로가 생겨 제대로 된 답을 계산할 수 없다. 이렇게 생각하면 무언가 떠올릴 수 있다. 부하의 칭찬을 나중에 한꺼번에 떠안자. 무슨 말이고 하면 정점 4에 5를 더하고 정점 2에 2를 더한 상태에서 정점 2의 칭찬도를 얻으려면 다음과 같이 할 수 있다. 아래로 값을 더하지 말고 2와 4의 값만 변경한 다음 2의 오일러 투어 구간 [2, 5]의 .. 백준 17408 - 수열과 쿼리 24 https://www.acmicpc.net/problem/17408 값을 바꾸는 것은 극히 기본적인 세그먼트 트리의 연산이지만 구간 내 두 원소의 합 중 최댓값을 가져오는 연산이 쉽지 않을 수 있다. 다시 생각하면 구간 내 두 원소의 합 중 최댓값은 구간 내에서 가장 큰 값 2개를 가지고 있는 것과 동일하며 해당 쿼리는 구간 내에서 가장 큰 2개의 값을 보존하는 문제로 바뀐다. 가장 큰 2개의 값을 보관하기 위해 C++ 기준 pair를 관리하는 세그먼트 트리를 구성하자. 그러면 왼쪽 절반 L에서 가장 큰 두 값을 저장하는 pair와 오른쪽 절반 R에서 가장 큰 두 값을 저장하는 pair를 가지고 다음 그림처럼 구간을 갱신할 수 있다. 위 그림처럼 가장 큰 두 개의 값을 들고 다니면 된다. 아는 사람은 짐.. 이전 1 2 3 4 5 다음
