题目大意

有 $n$ 棵高度互不相同的植物排成一个圆圈，按顺时针编号为 $0$ 到 $n-1$。对于每棵植物 $i$，我们知道在它顺时针方向的后 $k-1$ 棵植物中，有多少棵比它高（记为 $r_i$）。

需要回答 $q$ 个查询：对于植物 $x$ 和 $y$，判断是否一定能确定它们的高度关系。

解题思路

关键观察

1. 约束条件分析：每个 $r_i$ 实际上给出了一个局部约束。对于植物 $i$，在区间 $[i+1, i+k-1]$（模 $n$ 意义下）中，恰好有 $r_i$ 棵植物比 $i$ 高，$k-1-r_i$ 棵植物比 $i$ 矮。

2. 图论建模：我们可以将高度关系建模为有向图，如果已知 $u$ 比 $v$ 高，则添加边 $u \to v$。

3. 确定性判断：如果从 $x$ 到 $y$ 存在路径，则 $x$ 一定比 $y$ 高；如果从 $y$ 到 $x$ 存在路径，则 $x$ 一定比 $y$ 矮；否则无法确定。

算法步骤

步骤1：重建高度序列

我们需要从 $r$ 数组还原出一个可能的高度序列，这通过拓扑排序实现：

1. 维护每个位置当前"未知"的比较数量（初始为 $r_i$）
2. 当某个位置的未知比较数为 $0$ 时，说明它比其后 $k-1$ 个位置的所有植物都高，可以确定其相对高度
3. 使用线段树维护区间最小值，快速找到可确定的位置

步骤2：构建比较图

根据重建的高度序列，我们可以推断出一些确定的高度关系：

• 如果 $p[i] > p[j]$ 且 $j$ 在 $i$ 的后 $k-1$ 个位置内，则 $i$ 比 $j$ 高
• 使用倍增表 (nt 和 pv) 来快速判断两个位置之间是否存在确定的高度关系链

步骤3：回答查询

对于查询 compare_plants(x, y)：

1. 如果 $p[x] > p[y]$，则考虑 $x$ 是否一定比 $y$ 高
2. 检查是否存在从 $x$ 到 $y$ 的路径（考虑环形结构）
3. 如果存在，返回 $1$；如果存在从 $y$ 到 $x$ 的路径，返回 $-1$；否则返回 $0$

时间复杂度

• 初始化：$O(n \log n)$
• 每次查询：$O(\log n)$
• 总复杂度：$O(n \log n + q \log n)$