Tags

9 pages

Range Add

[Algorithm] cpp 백준 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] cpp 백준 16670번: King Kog의 접견실 - 세그먼트 트리

[Algorithm] C++ 백준 17955번 Max or Min

원형 배열에서 한 칸을 골라 인접 세 수의 최소/최대로 바꾸는 연산으로 모든 값을 x로 만드는 최소 시간을 구한다. 배열에 x가 없으면 불가능(-1). 인접 쌍마다 (min+1..max-1)에 1을 더하는 차분 누적으로 ‘그룹 수’를 집계하고, 시작점을 한 칸 회전한 두 번의 집계를 취해 중복을 보정한다. 정답은 (n - cnt[x]) + max(groups1[x], groups2[x])로 계산한다. O(n + m).
[Algorithm] C++ 백준 17955번 Max or Min