首先特判掉 $k=1$ 的询问。静态区间查询随便写点啥就行。

注意到区间 lca 一定是相邻两个数 lca 中最浅的一个。预处理原序列相邻两个数的 lca 的深度得出一个长为 $n-1$ 的新数列 $b_i$，一个询问转化为求 $\max_{l\leq p\leq q\leq r-1,q-p+1=k-1}(\min_{i=p}^qb_i)$。考虑整体二分，维护一个 01 序列 $c_i$ 表示 $b_i$ 是否 $\geq mid$。一个询问的答案 $\geq mid$ 当且仅当 $c$ 在 $[l,r-1]$ 中最长连续 $0$ 的长度 $\geq k-1$。用线段树维护 $c_i$，套上整体二分共 $O(n\log ^2n)$，赛时 5e5 的样例跑了 6s 出头（