BOJ 17353 : 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

https://www.acmicpc.net/problem/17353

17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

재밌는 문제이다.

우리는 느낌상 레이지 세그를 생각할 수 있지만, 더하는 값이 등차수열이기에 어떻게 해야할지 고민해봐야 한다.

이때, 우리는 인접한 두 배열 원소의 차이를 세그트리 원소로 하여 생각해보면, 결국 등차수열로 더하는게 어떤 구간 전체에 1을 더하는 것이랑 동치가 된다.

이때 두 원소의 차이를 저장하는 세그먼트 트리이기 때문에 구간의 마지막 원소를 잘 신경써주면서 구간합 레이지 세그를 돌리면 풀린다.

코드