[Tutorial] imos 알고리즘 timer 1초 memory 1024MB

imos 알고리즘 (또는 imos법)은 시작점과 끝점이 주어진 구간을 처리하는 데 유용한 기법이다.

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

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

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

• 우선 2에 2를 더하고, 4 다음 위치인 5에 -2를 더한다.

• 그 다음 3에 3을 더하고, 5 다음 위치인 6에 -3을 더한다.

• 마지막으로 처음부터 끝까지 누적하여 더해준다.

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

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

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

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

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