**【以下为原版做法】**

随着 $y$ 的值从 $0$ 增大到 $k^2-1$，格子与格子之间一共连上了 $2k(k-1)$ 条边，而这可以看成 $2k(k-1)$ 次加边操作。

在开始处理询问前，我们可以用并查集将 $2k(k-1)$ 次加边操作完整地维护一遍，并对每 $k$ 次操作分块。在每个块中，我们需要完整地保存此时并查集的状态，以及此时每个 $x$ 的取值对应的答案。

在并查集中，我们可以在每个连通块的根部记录该连通块的大小以及该连通块内的海拔。在每个 $x$ 的取值对应的答案时，我们只要扫描所有根部存储的信息，再结合前缀和就可以求出每个 $x$ 的取值对应的答案了。

对于每次询问，我们只需要访问其 $y$ 值对应的那一块，并在那一块的并查集上暴力进行剩下的加边操作，在加边的同时维护最终答案相对于之前存储的答案的变化，并在输出答案后复原并查集中被修改的部分，就可以做到在线回答询问了。

最终的时间复杂度为 $O(k^3+qk)$，空间复杂度为 $O(k^3)$。

**【以下为加强版（本题）做法】**

使用持久化权值线段树，对每个格子能走到的最低海拔位置开桶维护，即可完成优化。优化后的时间复杂度为 $O(k^2 \log k + q \log k)$，空间复杂度为 $O(k^2 \log k)$。