Posts tagged "segment-tree"

• 백준 24527번 이상한 나라의 갈톤보드

  2022년 3월 1일 · #binary-search #prefix-sum #segment-tree #cpp #imos #ps

  백준 24527번 이상한 나라의 갈톤보드 풀이. 구간 업데이트를 lazy segment tree와 imos 방식으로 각각 풀며 도착 구간 계산을 정리한다.
• 백준 17131번 여우가 정보섬에 올라온 이유

  2021년 12월 12일 · #segment-tree #cpp #ps #sweeping

  백준 17131번 여우가 정보섬에 올라온 이유 풀이. 좌우 스위핑으로 각 별보다 높은 별의 개수를 구하고 곱해 별자리 경우를 계산한다.
• 백준 13925번 수열과 쿼리 13

  2021년 12월 11일 · #segment-tree #cpp #ps

  백준 13925번 수열과 쿼리 13 풀이. 더하기, 곱하기, 대입 쿼리를 ax+b 형태의 lazy 값으로 합성해 처리한다.
• 백준 5419번 북서풍

  2021년 12월 11일 · #data-structure #segment-tree #cpp #ps #sweeping

  백준 5419번 북서풍 풀이. 좌표 압축과 세그먼트 트리를 이용해 정렬된 순서에서 조건을 만족하는 점 쌍의 수를 센다.
• 백준 13537번 수열과 쿼리 1

  2021년 12월 9일 · #sort #segment-tree #cpp #ps

  백준 13537번 수열과 쿼리 1 풀이. 머지 소트 트리의 정렬된 구간 벡터에서 upper_bound로 K보다 큰 원소 개수를 구한다.
• 백준 7469번 K번째 수

  2021년 12월 9일 · #binary-search #sort #segment-tree #cpp #ps

  백준 7469번 K번째 수 풀이. 머지 소트 트리로 구간 내 특정 값 이하의 개수를 구하고 이분 탐색으로 K번째 수를 찾는다.
• 백준 1395번 스위치

  2021년 12월 8일 · #segment-tree #cpp #ps

  백준 1395번 스위치 풀이. 켜진 스위치 개수와 반전 lazy 값을 저장해 구간 토글과 개수 질의를 처리한다.
• 백준 10999번 구간 합 구하기 2

  2021년 12월 7일 · #segment-tree #cpp #ps

  백준 10999번 구간 합 구하기 2 풀이. Lazy propagation으로 구간 업데이트를 미뤄 두고 필요한 순간에 합을 반영한다.
• 백준 12844번 XOR

  2021년 12월 7일 · #segment-tree #cpp #ps

  백준 12844번 XOR 풀이. XOR의 결합법칙과 교환법칙을 이용해 구간 XOR 쿼리와 lazy XOR 업데이트를 처리한다.
• 백준 5676번 음주 코딩

  2021년 12월 7일 · #segment-tree #cpp #ps

  백준 5676번 음주 코딩 풀이. 수를 양수, 음수, 0으로만 변환해 구간 곱의 부호를 세그먼트 트리로 빠르게 판단한다.
• 백준 1572번 중앙값

  2021년 12월 6일 · #segment-tree #cpp #ps

  백준 1572번 중앙값 풀이. 값 범위에 대한 세그먼트 트리를 만들고 슬라이딩 윈도우의 K번째 값을 찾아 중앙값 합을 구한다.
• 백준 2104번 부분배열 고르기

  2021년 12월 6일 · #divide-and-conquer #segment-tree #cpp #ps

  백준 2104번 부분배열 고르기 풀이. 구간 최솟값의 인덱스를 기준으로 분할 정복하며 부분배열 합과 최솟값의 곱을 최대화한다.
• 백준 2517번 달리기

  2021년 12월 5일 · #data-structure #segment-tree #cpp #ps

  백준 2517번 달리기 풀이. 실력을 좌표 압축한 뒤 세그먼트 트리로 앞선 선수 중 자신보다 강한 사람 수를 계산한다.
• 백준 7578번 공장

  2021년 12월 5일 · #segment-tree #cpp #ps

  백준 7578번 공장 풀이. 두 생산 라인의 같은 기계 위치를 매핑하고 세그먼트 트리로 교차하는 연결선 수를 센다.
• 백준 2243번 사탕상자

  2021년 12월 3일 · #binary-search #segment-tree #cpp #ps

  백준 2243번 사탕상자 풀이. 맛별 사탕 개수 합을 세그먼트 트리에 저장하고, 순위 기반 탐색으로 원하는 사탕 맛을 찾는다.
• 백준 9345번 디지털 비디오 디스크(DVDs)

  2021년 12월 3일 · #segment-tree #cpp #ps

  백준 9345번 디지털 비디오 디스크 풀이. 구간의 최솟값과 최댓값을 세그먼트 트리에 저장해 해당 범위의 DVD가 모두 있는지 확인한다.
• 백준 3653번 영화 수집

  2021년 12월 2일 · #segment-tree #cpp #ps

  백준 3653번 영화 수집 풀이. DVD 위치를 넉넉한 인덱스 영역에 배치하고 세그먼트 트리로 위에 쌓인 DVD 개수를 센다.
• 백준 1280번 나무 심기

  2021년 12월 1일 · #segment-tree #cpp #ps

  백준 1280번 나무 심기 풀이. 왼쪽과 오른쪽 나무의 개수와 거리 합을 세그먼트 트리에 저장해 새 나무의 비용을 계산한다.
• 백준 3006번 터보소트

  2021년 12월 1일 · #segment-tree #cpp #ps

  백준 3006번 터보소트 풀이. 세그먼트 트리로 남아 있는 원소 수를 세며 1, N, 2, N-1 순서의 이동 횟수를 계산한다.
• 백준 1517번 버블 소트

  2021년 11월 30일 · #segment-tree #cpp #ps

  백준 1517번 버블 소트 풀이. 실제 버블 정렬 대신 세그먼트 트리로 아직 정렬되지 않은 앞쪽 원소 수를 세어 swap 횟수를 구한다.
• 백준 6549번 히스토그램에서 가장 큰 직사각형

  2021년 11월 29일 · #divide-and-conquer #segment-tree #cpp #ps

  백준 6549번 히스토그램에서 가장 큰 직사각형 풀이. 최소 높이 막대를 기준으로 구간을 나누고 세그먼트 트리로 최솟값 인덱스를 찾는다.
• 백준 11505번 구간 곱 구하기

  2021년 11월 28일 · #segment-tree #cpp #ps

  백준 11505번 구간 곱 구하기 풀이. 세그먼트 트리에 구간 곱을 저장하고 업데이트 시 리프부터 부모 노드까지 값을 다시 계산한다.
• 백준 12837번 가계부 (Hard)

  2021년 11월 28일 · #segment-tree #cpp #ps

  백준 12837번 가계부 (Hard) 풀이. 값 변경이 아니라 누적 추가가 일어나는 구간 합 질의를 세그먼트 트리로 처리한다.
• 백준 2357번 최솟값과 최댓값

  2021년 11월 28일 · #segment-tree #cpp #ps

  백준 2357번 최솟값과 최댓값 풀이. 구간 최솟값 트리와 최댓값 트리를 각각 만들어 RMQ 질의에 답한다.
• 백준 2042번 구간 합 구하기

  2021년 11월 27일 · #segment-tree #cpp #ps

  백준 2042번 구간 합 구하기 풀이. 세그먼트 트리로 구간 합 질의와 단일 값 업데이트를 모두 O(log N)에 처리한다.