No.259

領域を2倍して $[0, N)$ の領域は右向きの魚, $[N, 2N)$ の領域は左向きの魚がいるとみなす. ただし $[N, 2N)$ の領域は水槽を反転しているものとする.

こうすることで, すべての魚は右向きに進むと考えることができる. (右端まで移動したら左端に戻る)

$t$ 秒に $y$ の位置に右向きの魚を投入するということは, $0$ 秒に $y - t$ の位置に魚を投入したことになり, $t$ 秒に $y$ の位置に左向きの魚を投入するということは, $2N - 1 - y - t$ の位置に魚を投入したことになる.

$t$ 秒に $[y, z)$ の領域の魚の数を数えるということは, $0$ 秒に $[y - t, z - t), [N - z - t, N - y - t)$ の領域の魚の数を数えることになる.

位置はいずれも $2N$ で割った余りを取る.

以上を Binary Indexed Tree で管理する.