$n$개의 노래의 길이가 주어진다. 광고를 마지막으로 본지 $c$시간이 지나면 다음 광고가 나오는데, $c$시간이 지났을 때 어떤 노래가 재생되고 있다면 그 노래가 끝난 후에 광고가 나온다. 모든 $1 \le i \le n$에 대해 $i$번째 노래부터 시작하여 $n$곡을 순서대로 모두 들었을 때 ($n$번째 노래 다음에는 $1$번째 노래로 돌아와서 계속 듣는다) 보게 될 광고의 개수를 모두 구하시오. 첫 곡을 재생하기 직전에 광고를 봤다고 가정하고, 첫 곡 직전과 마지막 곡 직후의 광고는 세지 않는다.

  • $1 \le n \le 10^6$
  • $1 \le c \le 10^9$
  • $1 \le d_i \le 10^3$ ($d_i$: $i$번째 노래의 길이)

접근

뭔가 세그먼트 트리 같은 것을 끼얹고 싶게 생겼는데, 앞 구간에서 마지막으로 광고를 본 지 얼마나 지났는가에 따라 뒤 구간에서 일어나는 일이 달라지기 때문에 잘 되지 않는다.

이 문제에서는 노래와 노래 사이에만 광고가 나온다는 것을 주목해야 한다. $i$번째 곡에서 시작하여 $x_1$곡을 들은 시점에 $y_1$번째 광고가 나오고, $i+x_1$번째 곡에서 시작하여 $x_2$곡을 들은 시점에 $y_2$번째 광고가 나온다면, $i$번째 곡에서 시작하여 $x_1 + x_2$곡을 들은 시점에는 $y_1 + y_2$번째 광고가 나올 것이다.

모든 $i$에 대해 $i$번째 곡에서 시작하여 첫 광고를 볼 때까지 들은 곡의 수는 투 포인터로 총 $\mathcal{O}(n)$에 셀 수 있다. 예외적으로 만약 $\sum_i {d_i} \le c$이면 $c$시간을 채우기 위해 10억 곡을 도는 참사가 발생할 수 있으므로 따로 처리하고 종료한다. 이 경우 답은 0 0 0 ... 0이다.

첫 광고를 볼 때까지 들은 곡의 수를 계산했으므로, 이제 table[k][i] = $i$번째 곡에서 시작하여 $2^k$번째 광고를 보기까지 들은 곡의 수를 계산할 수 있다. 이것 자체는 전형적인 sparse table이지만 대놓고 functional graph나 LCA 문제가 아니면 떠올리기 어려운 것 같다. 이러한 table을 계산했으면, $n$곡을 들었을 때까지 본 광고의 수는 sparse table 기반 LCA의 후반부에 나오는 이분 탐색을 똑같이 이용하면 된다. 시간 복잡도는 테이블 구성과 테이블을 이용한 이분탐색 모두 $\mathcal{O}(n \log n)$이다.