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

레이지 세그를 공부하던 중 만난 문제다..

그냥 딱 보면 이게 뭐지 싶은 발상이 쉽지 않았다.

 

문제에는 2가지 쿼리가 주어진다.

 

• 1 l r : $\sum_{i=l}^{r}A_i+i-l+1$ 을 한다.
• 2 x : $A_i$ 의 값을 출력한다.

 

문제에서 1번 쿼리를 하면 $\sum_{i=l}^{r}A_i+i-l+1$을 하기 때문에 일반적인 구간 합 구하기 방법으로는 찾기 힘들다. 그렇다면 어떤 방법을 사용해야 될까에 대해 고민해 봐야 되는데 여기서 누적합을 응용하면 문제가 단순하게 변한다. 

여기 예제 1번을 보자

1 2 1 2 1

 

여기서 누적합은 앞에 저장된 수를 더하지만 이번엔 앞에 수로 빼보자

1 1 -1 1 -1

이 상태에서 누적합을 하면 다시 처음 상태로 복원되는 것을 확인할 수 있다.

 

그럼 이걸 가지고 무엇을 할 수 있을까?

구간에 출입을 기록할 수 있다.

에..?

뭔소린가 싶다.

여기서 출입은 l, r구간에 v를 더한다고 가정하면 l번째 수에 +v를 하고 r+1번째에 -v를 하는 것이다.

그러면 이러한 쿼리를 전부 실행한 후 배열을 다시 복원하면 원하는 수를 구할 수 있다!

 

하지만 이 문제의 쿼리는 증가하는 형태로 더해진다.

그렇다면 각 i에 1씩 더하고 r+1에 r-l+1을 빼주면 된다!

 

1번 쿼리를 해결했으니 2번 쿼리는 쉽다.

누적합을 사용하면 배열이 복구가 됨을 이용해 1~x까지의 구간합이 찾고자 하는 $A_x$와 같다.