이진 인덱스 트리와 세그먼트 트리를 활용한 효율적인 알고리즘 해결 방안
이 문제는 주로 자료구조를 다루며, O(n log²n) 시간 복잡도를 가지는 이진 인덱스 트리와 이분 탐색 조합이 O(n log n)의 세그먼트 트리 이분 탐색보다 빠르다는 점을 보여줍니다. 세그먼트 트리는 상수 최적화가 필요할 정도로 20ms 차이로 시간 초과가 발생합니다.
공식을 통해 k 라운드(모두 사용) 후 체력이 0이 되는 지점을 이분 탐색으로 찾을 수 있습니다. 그 다음 ...
7월 25일 13:03에 게시됨
CDQ 분할 정복 기법을 활용한 다차원 쿼리 처리
CDQ 분할 정복 개요
CDQ 분할 정복은 복수의 쌍 (i, j)에 대해 왼쪽 구간과 오른쪽 구간 간의 상관 관계를 효율적으로 계산하는 기법입니다. 이는 주로 순서가 중요한 쿼리 문제에서 사용되며, 분할과 정복 과정 중에 왼쪽 데이터가 오른쪽 데이터에 미치는 영향을 집계합니다.
문제 예시: 3차원 편향 쿼리 (P3810)
각 요소는 세 가지 차원 a, b, c로 구성되며, 조건 a_i ...
6월 27일 17:05에 게시됨