本文主要是介绍（CSP2019模拟）DTOJ 4628. 黎明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
有一片云海形成的世界，有陆地有海洋，可以看作 R × C R \times C R×C 的网格。
随着岁月的变迁，有时候水位上涨，一部分区域会变成水道。
神奇的是，每次变成水道的区域都是一个矩形。(若这个矩形中有一部分原来就是水道，那么这部分不变，其他为陆地的部分变成水道)
有时候这个世界上会有人想从 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 通过在水道中乘船到 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)，问能否到达。(当然 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 或 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 为陆地时显然不能)。
【提示】
R , C R,C R,C 不在输入中给出，请自行统计数据特征。
| 测试点编号 | Q Q Q | R R R | C C C | 特殊限制 |
|---|---|---|---|---|
| 1~3 | ≤ 1000 \le 1000 ≤1000 | ≤ 50 \le 50 ≤50 | ≤ 1000 \le 1000 ≤1000 | 无 |
| 4~5 | ≤ 200000 \le 200000 ≤200000 | = 1 =1 =1 | ≤ 100000 \le 100000 ≤100000 | 无 |
| 6~7 | ≤ 200000 \le 200000 ≤200000 | ≤ 3 \le 3 ≤3 | ≤ 100000 \le 100000 ≤100000 | o p t = 0 opt=0 opt=0 时 y 1 = y 2 y_1=y_2 y1=y2 |
| 8~10 | ≤ 200000 \le 200000 ≤200000 | ≤ 50 \le 50 ≤50 | ≤ 100000 \le 100000 ≤100000 | 无 |
题解
考场：不知道为什么看错了很久的题，一直以为要求最短路，自闭了半天。后来发现只要询问联通性，由R=1的部分分联想到用并查集维护每个点所在行的联通块的右端点，每次一个一个联通快进行修改，以保证效率。对于不同行之间，再把每行联通块的右端点用并查集维护联通性，修改时每行修改完成为一个联通块，每行之间连起来（这个东西没想清楚），再算上对前后两行的影响。但细节繁琐码量较大，打到一半就弃了。
对于前后两行的影响，可直接在第一行和最后一行原来的每个联通块的末尾的位置，在前后两行查找所在联通块，如果是水就连上去即可。（虽然细节还是很多调到自闭）
upd：
其实根本没必要这样，对于每一行维护每个点的下一个不是水的位置，每覆盖一个矩形就新建一个点，把不是水的位置和查找过程中经过的并查集连向该矩形，就可简单维护了。
这篇关于（CSP2019模拟）DTOJ 4628. 黎明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
