树上查询
Eterna
·
·
个人记录
设 a_i=\mathrm{dep}_{\mathrm{LCA}^{*}(i,i+1)}。对于 l<r，可以发现
\mathrm{dep}_{\mathrm{LCA}^{*}(l,r)}=\min_{i=l}^{r-1}a_i
我们令 r \gets r-1,k \gets k-1。
于是问题变为求与询问区间 [l,r] 中长度至少为 k 的区间中 \min 的 \max。
从大到小加入 a_i，维护 \mathcal{O}(n) 个极长连续段 (x_j,y_j,v_j) 表示 x_j \le i \le y_j 均有 a_i \ge v_j。每次询问考虑 [l,r] 和 [x_j,y_j] 的交集大小 \ge k 即可。
对于“交集大小至少为 k”，我们可以写出两个不等式，满足其一即可：
y_j\ge r\land x_j\le r-k+1 \\
l+k-1\le y_j\le r\land y_j-x_j+1\ge k
两个都可以在 \mathcal{O}(n \log n) 的时间复杂度内求解。