思路分析

可证：要求一段区间中大于等于 $k$ 的自区间中所有节点的最近公共祖先深度的最大值，那么这个子区间的长度一定等于 $k$（试想如果再增加一个点，那么这个深度要么不变要么变浅，不可能变深）。

那么我们可以预处理一个类似于线段树的数据结构（和去掉修改操作的线段树类似）出来，设任意一个非叶子节点所包含的区间为 $[x,y]$，左孩子包含的区间为 $[x,\frac{x+y}{2}]$，右孩子包含 $[\frac{x+y}{2}+1,y]$，每个节点同时还存下这个区间所有节点的最近公共祖先。

最后，我们暴力枚举每个长度为 $k$ 的子区间，运用类似于线段树的方式求解所有节点的最近公共祖先，并计算每个子区间深度的最大值。

时间复杂度计算

对于倍增的 LCA，预处理时间复杂度为 $O(n log n)$，之后每次查询时间复杂度是 $O(log{n})$ 。

对于构建类似于线段树的这种数据结构，是 $O(n log n)$ 的（共有 $2n-1$ 个节点，由于是大 O 表示法，所以略去常数）。

对于枚举区间，时间复杂度为 $O(n log n)$（$O(n)$ 用于枚举，$O(log n)$ 用于查询）。

所以总时间复杂度为 $O(n log n)$。

经过带入数据范围，发现理论上并不会超时。

我的疑问

在考场，我也成功实现了这个思路，经过测试发现，样例 $1~3$ 均可以通过，但是样例 $4$ 超时挺多，我没等跑完就把程序掐了，所以不知道对不对，但前几个样例都对了。

好奇是我思路有误还是实现有误（有点担心是我数组开小了）