2018 German Collegiate Programming Contest (GCPC 18)
M
题意
二维网格图，每个点有一个值，q 次询问从 $(x_1, y_1)$ 走到 $(x_2, y_2)$ 所经过的格子中值最大的要最小。
题解
并查集启发式合并。
- 从小到大枚举高度，不断添加不大于当前高度的块，连通的块一定是互相可达而且当前枚举值一定可达。
- 考虑可以合并的两个连通块。
- 显然需要启发式的合并，即小的集合合并到大的上面。
- 并对两个连通块所包含的询问进行回答，用一个 $set$ 维护。