小蒟蒻用可持久化线段树乱搞了一个 $\mathcal{O}(n \log n)$ 的在线做法。

但是可持久化线段树模板的难度评级本身已经超出了LCA模板的难度评级，所以在想可不可以写一篇题解向管理员投稿。