본문 바로가기

segment tree

BOJ 10775 공항 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 숫자가 1부터 G까지 하나씩 있는 집합 A가 있을 때 주어진 숫자 x에 대해 아래의 연산을 수행한다. 집합 A에서 x보다 작거나 같은 원소 중 가장 큰 숫자를 찾는다. 위에서 찾은 원소를 A에서 제거한다. 위에서 찾은 원소를 반환한다. 일감은 구간 트리(segment tree)를 이용하여 해결하는 것이다. 구간 트리에 대해서 i번째 원소를 i로 초기화 한다. x에.. 더보기
BOJ 12858 Range GCD https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net gcd(a, b, c, d, e) = gcd(a, |b - a|, |c - b|, |d- c|, |e - d|) 임을 이용해야 한다. (이 부분이 핵심이다) 어떤 구간에 속한 모든 원소에 x를 더한 더하는 경우, 그 구간 내에서 이웃한 원소들 사이의 차이는 변화가 없다. 그 구간의 경계에 인접한 원소와의 차이에만 변화가 발생한다. GCD를 계산하기 위한 세그먼트 트리에는 인.. 더보기
BOJ 17429 국제 메시 기구 https://www.acmicpc.net/problem/17429 17429번: 국제 메시 기구 첫째 줄에 N, Q가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 100,000) 다음 N-1줄 중 i번째 줄에는 Si, Ei가 주어지며, 이는 금고 Si와 금고 Ei가 연결되어 있다는 뜻이다. (1 ≤ Si, Ei ≤ N) 금고가 연결된 모 www.acmicpc.net 1감은 HLD를 이용한 풀이인데, 서브 트리 쿼리 처리를 어떻게 하는지에서 생각하느라 고생을 많이 했다. 우선 서브 트리 쿼리는 오일로 경로 테크닉을 이용해서 트리를 일자로 늘어뜨리면 해결이 된다. 트리를 순회(preorder traverse)하면서 노드의 발견 시각과 종료시각을 기록한다. 노드의 발견시각을 그 노드의 인덱스로 .. 더보기
BOJ 5466 상인 (IOI 2009 Salesman) https://www.acmicpc.net/problem/5466 5466번: 상인 어떤 상인이 육지에서 최적 여행 스케줄을 구하는 것이 매우 어려웠기 때문에, 직선으로 흐르는 다뉴브강을 따라 이동하면서 물건을 팔기로 했다. 이 상인은 다뉴브 강을 따라 임의의 위치로부 www.acmicpc.net 문제 분석 단계에서 아래의 성질을 이용할 수 있지 않을까를 고민하다 결국 더 오래 걸린 문제 상인은 결국 시작점으로 돌아와야 한다. 따라서 올라간 거리의 합 = 내려간 거리의 합. DP 식을 잘 조작을 해서 컨벡스 홀 최적화나, 크누스 최적화를 적용하기. 위의 조건을 잊어버리고 그냥 각 경우 별 DP 점화식을 생각해 보면, 우선 시장들을 시장이 열리는 날짜 순으로 정렬을 한 뒤, DP[i] = i 번째 시장을 .. 더보기

티스토리툴바