到底谁会虚树啊，

先把所有询问离线对右端点扫描线，然后依次将每个数放入点分树中。以下设 $u,v$ 分别为插入的和询问的节点，$x,y$ 为插入的时刻和询问的左端点。

• $u,v$ 均在分治中心下方

此时插入节点和询问节点的 LCA 为分治中心，所以维护所有 $x$ 的最大值即可，如果 $x\geq y$ 则可以造成贡献。

注意 $u,v$ 不能在同一个子树内，所以需要记录最大的两个不同子树值。

• $u$ 在分治中心下方，$v$ 在分治中心上方

此时和上面类似，不过 LCA 和 $v$ 有关，记录所有 $v$ 和分治中心的 LCA 即可。

• $u$ 在分治中心上方，$v$ 在分治中心下方

此时需要维护所有插入点的时刻和与分治中心的 LCA。

我们发现对于 $x_1< x_2$ 并且 $v_1$ 对应的 LCA 小于 $v_2$ 对应的 LCA，那么前面那个点就没有用。所以实际上维护每个分治中心的单调栈即可，查询时在单调栈上二分。

为了做到一只 $\log$，我们把每个分治中心插入的所有元素二次离线，发现分别形成树结构，刚才的二分本质上是在求这棵树上的 LCA，写个 $O(1)$ LCA 即可。或者可以用 https://blog.rijuyuezhu.top/posts/34e7c893/4.pdf 这个科技。

总复杂度 $O(n\log n)$，常数较小。