自动搬运

查看原文

来自洛谷，原作者为

	FlierKing **

搬运于2025-08-24 21:53:04，当前版本为作者最后更新于2017-07-01 21:47:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

##对于30%的数据

对于每个点的询问，我们可以直接暴力BFS，直接比较即可。

##对于70%的数据

直接将图存在一个$1000\times 1000$的数组里。然后将每个联通块的块的大小存在一个点上。如果将温泉变为土，由于不会将一个块分割，所以直接v[fa(x)]--即可；如果将土变为温泉，那么为这块地新开一个位置，然后将这个点四周的大小合并到这个点上即可。以上均可以用并查集来维护。

##对于100%的数据

只需在70分的基础上加一些小技巧将图存在一个$10^{6}$的数组里即可。

另外，不推荐使用在原位置直接重开点的方法维护大小，可能会导致一些本不联通的联通块的数据联通的情况。

以上为被dalaoD翻的水题题解

最后感谢Ditoly和FallDream帮助验题。