BOJ 17353 : 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별
https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 재밌는 문제이다. 우리는 느낌상 레이지 세그를 생각할 수 있지만, 더하는 값이 등차수열이기에 어떻게 해야할지 고민해봐야 한다. 이때, 우리는 인접한 두 배열 원소의 차이를 세그트리 원소로 하여 생각해보면, 결국 등차수열로 더하는게 어떤 구간 전체에 1을 더하는 것이랑 동치가 된다. 이때 두 원소의 차이를 저장하는 세그먼트 트리이기 때문에 구간의 마지막 원소를..
2021.08.17