本人不才，使用了 ST LCA，预计复杂度 $\Theta(n\log n+xq)$，$x$ 为常数，大约 20，用 scanf 才能过！！！