rt，拆位是经典套路，离线然后按位处理思维难度也不高（类似分块然后逐块处理）。

以及题目描述最后一行：

他知道引力波的频率可能很高，所以你只需要告诉她答案 $\bmod2^{30}$ 的值就可以了。

是 typo 吗？