"차분 배열 트릭(Difference Array Technique)"은 시작점과 끝점이 주어진 구간을 처리하는 데 유용한 기법이다.

각 지점에서의 변경 값을 저장하고 누적하여 계산함으로써 가장 중첩되는 영역을 구할 수 있는데, 쿼리 처리 도중 값 갱신이 일어나지 않는 경우에 사용된다.

각 쿼리가 구간 [s, e] 내의 값을 갱신시키는 경우, 이를 매 쿼리마다 일일히 갱신하지 않고, 시작과 끝만 기록해두었다가 마지막에 한 번의 처리로 값을 처리해주는 방법이다.

예를 들어 [2, 4] 구간에 2를 더하고, [3, 5] 구간에 3을 더한다면,

아래 문제를 풀어보며 자세한 감을 잡아보자.

[문제]
이모스씨의 라멘집에는 오늘 N팀의 손님들이 방문했다.

각 i번째 팀은 C_i명의 사람들로 이루어져 있으며 S_i 시간에 입장하여 E_i 시간까지 가게에 있다가 떠났다.

이모스씨의 라멘집의 사장님은 T_j 시간에 대하여 몇 명의 손님이 있었는지 Q번 물어본다.

이를 출력해주는 프로그램을 작성하시오.

Tutorial : 차분 배열 트릭 (Difference Array Technique) timer 1s memory 1024MB

Tutorial : 차분 배열 트릭 (Difference Array Technique) 1s 1024MB