详见本题解

大概就是每个点往后扩展 $\sqrt n$ 个，处理完所有询问后进行合并。