백준 24527번 이상한 나라의 갈톤보드
구간 업데이트를 lazy 세그먼트 트리와 imos 차분 배열 두 가지로 풀고 도착 구간 계산하기
모든 태그
주제
#segment-tree
글 25개
-
-
백준 17131번 여우가 정보섬에 올라온 이유
왼쪽과 오른쪽으로 한 번씩 스위핑하며 자기보다 높은 별 수를 세어 곱하기, 같은 x좌표 처리 주의
-
백준 13925번 수열과 쿼리 13
더하기, 곱하기, 대입 쿼리를 ax+b 형태의 lazy 값 하나로 합성하는 세그먼트 트리
-
백준 5419번 북서풍
x좌표로 정렬하고 압축한 y좌표를 세그먼트 트리에 기록해 북서풍 조건을 만족하는 쌍 세기
-
백준 13537번 수열과 쿼리 1
합병 정렬의 중간 결과를 저장한 머지 소트 트리에서 upper_bound로 K보다 큰 원소 수 세기
-
백준 7469번 K번째 수
머지 소트 트리로 구간에서 어떤 값 이하인 수의 개수를 구하고 이분 탐색으로 K번째 수 찾기
-
백준 1395번 스위치
켜진 스위치 수와 반전 횟수를 lazy로 저장하고 홀수일 때만 뒤집는 구간 토글
-
백준 10999번 구간 합 구하기 2
구간 업데이트를 바로 반영하지 않고 표시만 해 두었다가 방문할 때 밀어 넣는 lazy propagation
-
백준 12844번 XOR
결합·교환 법칙이 성립하는 XOR로 만든 세그먼트 트리와 lazy 전파, += 대신 ^=를 써야 하는 이유
-
백준 5676번 음주 코딩
값을 1, 0, -1로만 바꿔 곱하는 세그먼트 트리로 구간 곱의 부호 판정하기, EOF까지 입력받기
-
백준 1572번 중앙값
값 범위로 만든 세그먼트 트리에서 슬라이딩 윈도우의 K번째 값을 찾아 중앙값 합 구하기
-
백준 2104번 부분배열 고르기
구간 최솟값의 위치를 기준으로 좌우를 나누는 분할 정복, 히스토그램 문제와 같은 구조
-
백준 2517번 달리기
실력을 좌표 압축하고 세그먼트 트리로 앞선 선수 중 자기보다 강한 사람 수 세기
-
백준 7578번 공장
A열 위치를 기계 번호로 기록하고 세그먼트 트리로 교차하는 연결선 수 세기, int 범위 주의
-
백준 2243번 사탕상자
맛별 사탕 개수 합을 세그먼트 트리에 두고 순위를 따라 내려가며 원하는 사탕 찾기
-
백준 9345번 디지털 비디오 디스크(DVDs)
구간 최솟값과 최댓값이 L과 R과 같은지 세그먼트 트리로 확인해 DVD가 제자리인지 판정하기
-
백준 3653번 영화 수집
배열 앞쪽에 빈 자리를 비워 두고 DVD를 맨 위로 옮기며 세그먼트 트리로 위에 쌓인 개수 세기
-
백준 1280번 나무 심기
구간의 나무 개수와 거리 합을 세그먼트 트리에 두고 새 나무를 심는 비용을 바로 계산하기
-
백준 3006번 터보소트
버블 소트 풀이에서 쿼리 순서만 1, N, 2, N-1로 바꿔 세그먼트 트리로 이동 횟수 세기
-
백준 1517번 버블 소트
실제로 버블 정렬하지 않고 세그먼트 트리로 앞쪽의 정렬되지 않은 원소 수를 세어 swap 횟수 구하기
-
백준 6549번 히스토그램에서 가장 큰 직사각형
가장 낮은 막대를 기준으로 구간을 나누는 분할 정복, 최솟값 위치는 세그먼트 트리로 찾기
-
백준 11505번 구간 곱 구하기
구간 합 대신 구간 곱을 저장하는 세그먼트 트리, 범위 밖이면 1을 반환하고 리프부터 다시 곱하는 업데이트
-
백준 12837번 가계부 (Hard)
값을 바꾸는 대신 더하는 쿼리라는 점만 주의하면 되는 구간 합 세그먼트 트리
-
백준 2357번 최솟값과 최댓값
구간 최솟값 트리와 최댓값 트리를 따로 만들어 RMQ 질의에 답하기
-
백준 2042번 구간 합 구하기
구간 합 질의와 값 변경을 모두 O(log N)에 처리하는 세그먼트 트리 기본 구현