Problem Solving (98) 썸네일형 리스트형 백준 2844번 자료구조 백준 2844번 자료구조 스플레이트리를 사용해서 문제를 해결할 수 있다. 3번과 4번쿼리는 별 거 없이 스플레이 트리의 기본 연산들로 처리할 수 있다. (split, merge) 1번쿼리 또한 레이지 프롭으로 쉽게 해결이 가능한 쿼리다. 2번 쿼리가 문제다. 스플레이트리로 선형 배열을 다룰 때 서브트리는 각각 어떤 구간을 담당하고 있는 것으로 볼 수 있다. [L, R]을 담당하게 서브트리를 잘 모았다고 치면 이 구간에 들어오는 2번 쿼리는 초항이 X이고 공차가 X이며 길이가 R-L+1인 수열을 [L, R]에 더해주는 것이다. 그러면 이 쿼리를 어떻게 전파할 지 생각할 수 있다. 해당 서브트리의 루트가 위 구간에서 m번째 노드라고 하자. 그러면 왼쪽 서브트리는 [L, m-1]을 담당하고 오른쪽 서브트리는 .. BOJ 백준 16296번 Daily division BAPC 2018 Preliminary D번 문제이다. 풀이에 앞서 문제를 먼저 정리하자면, 1번 부터 N번까지의 마을이 일렬로 있으며 각 마을에 몇 명이 있는지가 주어진다. 날마다 푸드트럭이 이 마을로 찾아오는데 i번 마을에 찾아왔을 때 1번부터 i-1번 마을까지의 사람들이 왼쪽에 줄을 서고, i+1번부터 N번 마을까지의 사람들이 오른쪽에 줄을 서게 된다. i번 마을에 있는 사람들은 반으로 나눠져 각각 왼쪽 오른쪽에 서며, 사람 수가 홀수일 경우에는 남는 1명은 양쪽 줄의 차이가 적어지는 쪽으로 이동하되, 양쪽 사람 수가 같으면 아무 곳이나 간다. 이 때, 쿼리는 i번 마을의 사람 수가 임의로 바뀌었을 때 양쪽 줄의 차이가 가장 적어지는 푸드 트럭의 위치는 어디인가이다. 트럭이 i번 마을에 왔을 때, .. 이전 1 ··· 10 11 12 13 다음