Tags

53 pages

세그먼트 트리

[Algorithm] C++ 백준 16670번: King Kog의 접견실 - 세그먼트 트리

기사들의 방문(도착 시각 t, 소요 d)이 실시간으로 추가/취소되는 상태에서 공주가 시각 t에 도착했을 때의 대기 시간을 즉시 구합니다. 누적 처리량 P(t)와 선형 시간 t를 결합한 백로그 공식 W(t) = (P(t) - t) - min_{u≤t}(P(u) - u) 를 활용하고, 좌표 압축 + 지연 전파 세그먼트 트리로 접수/취소는 suffix 가산, 질의는 점/구간 최소를 O(log N)에 처리해 q ≤ 3e5를 안정적으로 통과합니다.
[Algorithm] C++ 백준 16670번: King Kog의 접견실 - 세그먼트 트리

[Algorithm] C++ 백준 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 - PBS+세그트리

히스토그램의 구간 [l,r]에서 너비 w가 고정일 때 최대 넓이는 길이 w 윈도우의 최솟값을 최대화하는 문제입니다. 높이 좌표압축과 임계값 단조성을 이용해 병렬 이분탐색을 수행하고, 세그먼트 트리(연속 1의 최댓값)로 검증하여 각 쿼리를 빠르게 해결합니다. 엣지 케이스와 실수 포인트까지 점검합니다.
[Algorithm] C++ 백준 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 - PBS+세그트리

[Algorithm] C++ 백준 24272번: 루트 노드가 많은 트리일수록 좋은 트리이다

유일 경로 트리의 간선 방향을 제어하며 ‘모든 정점에 도달 가능한 루트’의 수를 유지하는 문제입니다. Euler tour로 서브트리를 구간화하고, child→parent 제약의 교집합과 parent→child 제약의 합집합을 각각 multiset과 세그먼트 트리로 관리하여 매 쿼리 O(log N)에 정답을 계산합니다. 엣지 케이스(교집합 공집합, 전역 인터벌, 무방향 전환)까지 안정적으로 처리합니다.
[Algorithm] C++ 백준 24272번: 루트 노드가 많은 트리일수록 좋은 트리이다

[Algorithm] C++ 백준 3319번: 전령들

트리의 각 도시에서 수도까지 메시지를 가장 빨리 전달하는 최소 시간을 구하는 문제입니다. 도시 i는 출발 준비 시간 S_i와 1km당 이동 시간 V_i를 가지며, 유일한 최단 경로를 따라 이동 중 중간 도시에서 다른 전령에게 넘길 수 있습니다. dp[u]를 루트까지의 거리 dist[u]를 이용해 dp[u] = S_u + V_u·dist[u] + min_{조상 x}(dp[x] − V_u·dist[x])로 정리하고, 조상 집합에 대한 직선 최소값 질의를 처리하기 위해 Li Chao Tree(선형함수 컨벡스 헐 트릭)를 트리 경로에 영속적으로 유지(퍼시스턴스)하여 각 정점에서 O(log C)에 답합니다. 64비트 정수 및 곱셈 시 128비트 캐스팅으로 오버플로를 방지합니다.
[Algorithm] C++ 백준 3319번: 전령들

[Algorithm] C++ 백준 8987번: 수족관 3 - 카르테시안 트리

수평 바닥을 구간 높이 배열로 모델링한 뒤, 최소 높이 기준으로 구간을 분할하는 카르테시안 트리를 구성해 각 노드 직사각형 넓이를 계산합니다. 분할로 얻는 이득을 우선순위 큐에 넣어 상위 K개를 합하면 최대 배수량을 얻습니다. 구현은 O(N)~O(N log N)으로 안정적이며, 64-bit 정수 오버플로와 구간 경계 처리, 입력 형식 차이 등을 면밀히 점검합니다.
[Algorithm] C++ 백준 8987번: 수족관 3 - 카르테시안 트리